Search

Clustering algorithms are fundamental tools in data analysis, with hierarchical methods being particularly valuable for their flexibility. Chameleon is a widely used hierarchical clustering algorithm that excels at identifying high-quality clusters of arbitrary shapes, sizes, and densities. Chameleon2 is the most recent variant that has demonstrated significant improvements, but suffers from critical failings and there are certain improvements that can be made. The first failure we address is that the complexity of Chameleon2 is claimed to be $O(n^2)$, while we demonstrate that it is actually $O(n^2\log{n})$, with $n$ being the number of data points. Furthermore, we suggest improvements to Chameleon2 that ensure that the complexity remains $O(n^2)$ with minimal to no loss of performance. The second failing of Chameleon2 is that it lacks transparency and it does not provide the fine-tuned algorithm parameters used to obtain the claimed results. We meticulously provide all such parameter values to enhance replicability. The improvement which we make in Chameleon2 is that we replace the exact $k$-NN search with an approximate $k$-NN search. This further reduces the algorithmic complexity down to $O(n\log{n})$ without any performance loss. Here, we primarily configure three approximate nearest neighbor search algorithms (Annoy, FLANN and NMSLIB) to align with the overarching Chameleon2 clustering framework. Experimental evaluations on standard benchmark datasets demonstrate that the proposed Chameleon2++ algorithm is more efficient, robust, and computationally optimal., Comment: 29 Pages, 15 Figures, 12 Tables

We present the first formal correctness proof of Edmonds' blossom shrinking algorithm for maximum cardinality matching in general graphs. We focus on formalising the mathematical structures and properties that allow the algorithm to run in worst-case polynomial running time. We formalise Berge's lemma, blossoms and their properties, and a mathematical model of the algorithm, showing that it is totally correct. We provide the first detailed proofs of many of the facts underlying the algorithm's correctness.

Imperfect-recall games, in which players may forget previously acquired information, have found many practical applications, ranging from game abstractions to team games and testing AI agents. In this paper, we quantify the utility gain by endowing a player with perfect recall, which we call the value of recall (VoR). While VoR can be unbounded in general, we parameterize it in terms of various game properties, namely the structure of chance nodes and the degree of absentmindedness (the number of successive times a player enters the same information set). Further, we identify several pathologies that arise with VoR, and show how to circumvent them. We also study the complexity of computing VoR, and how to optimally apportion partial recall. Finally, we connect VoR to other previously studied concepts in game theory, including the price of anarchy. We use that connection in conjunction with the celebrated smoothness framework to characterize VoR in a broad class of games., Comment: 36 pages, 6 figures, main body to be published in Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25), Philadelphia, Pennsylvania, USA, 2025

Student placements under diversity constraints are a common practice globally. This paper addresses the selection of students by a single school under a \emph{one-to-one convention}, where students can belong to multiple types but are counted only once based on one type. While existing algorithms in economics and computer science aim to help schools meet diversity goals and priorities, we demonstrate that these methods can result in significant imbalances among students with different type combinations. To address this issue, we introduce a new property called \emph{balanced representation}, which ensures fair representation across all types and type combinations. We propose a straightforward choice function that uniquely satisfies four fundamental properties: maximal diversity, non-wastefulness, justified envy-freeness, and balanced representation. While previous research has primarily focused on algorithms based on bipartite graphs, we take a different approach by utilizing flow networks. This method provides a more compact formalization of the problem and significantly improves computational efficiency. Additionally, we present efficient algorithms for implementing our choice function within both the bipartite graph and flow network frameworks., Comment: A shorter version of this paper was published in the Proceedings of the 39th AAAI Conference on Artificial Intelligence

We study the Boolean Satisfiability problem (SAT) in the framework of diversity, where one asks for multiple solutions that are mutually far apart (i.e., sufficiently dissimilar from each other) for a suitable notion of distance/dissimilarity between solutions. Interpreting assignments as bit vectors, we take their Hamming distance to quantify dissimilarity, and we focus on problem of finding two solutions. Specifically, we define the problem MAX DIFFER SAT (resp. EXACT DIFFER SAT) as follows: Given a Boolean formula $\phi$ on $n$ variables, decide whether $\phi$ has two satisfying assignments that differ on at least (resp. exactly) $d$ variables. We study classical and parameterized (in parameters $d$ and $n-d$) complexities of MAX DIFFER SAT and EXACT DIFFER SAT, when restricted to some formula-classes on which SAT is known to be polynomial-time solvable. In particular, we consider affine formulas, $2$-CNF formulas and hitting formulas. For affine formulas, we show the following: Both problems are polynomial-time solvable when each equation has at most two variables. EXACT DIFFER SAT is NP-hard, even when each equation has at most three variables and each variable appears in at most four equations. Also, MAX DIFFER SAT is NP-hard, even when each equation has at most four variables. Both problems are W[1]-hard in the parameter $n-d$. In contrast, when parameterized by $d$, EXACT DIFFER SAT is W[1]-hard, but MAX DIFFER SAT admits a single-exponential FPT algorithm and a polynomial-kernel. For 2-CNF formulas, we show the following: Both problems are polynomial-time solvable when each variable appears in at most two clauses. Also, both problems are W[1]-hard in the parameter $d$ (and therefore, it turns out, also NP-hard), even on monotone inputs (i.e., formulas with no negative literals). Finally, for hitting formulas, we show that both problems are polynomial-time solvable., Comment: 27 pages, 5 figures; this is full version of the corresponding paper accepted and presented at the 35th International Symposium on Algorithms and Computation (ISAAC 2024)

We show that for every first-order logic (FO) formula $\varphi$, and every graph class $\mathcal{G}$ of bounded expansion, there exists a distributed (deterministic) algorithm that, for every $n$-node graph $G\in\mathcal{G}$ of diameter $D$, decides whether $G\models \varphi$ in $O(D+\log n)$ rounds under the standard CONGEST model. Graphs of bounded expansion encompass many classes of sparse graphs such as planar graphs, bounded-treedepth graphs, bounded-treewidth graphs, bounded-degree graphs, and graphs excluding a fixed graph $H$ as a minor or topological minor. Note that our algorithm is optimal up to a logarithmic additional term, as even a simple FO formula such as "there are two vertices of degree 3" already on trees requires $\Omega(D)$ rounds in CONGEST. Our result extends to solving optimization problems expressed in FO (e.g., $k$-vertex cover of minimum weight), as well as to counting the number of solutions of a problem expressible in a fragment of FO (e.g., counting triangles), still running in $O(D+\log n)$ rounds under the CONGEST model. This exemplifies the contrast between sparse graphs and general graphs as far as CONGEST algorithms are concerned. For instance, Drucker, Kuhn, and Oshman [PODC 2014] showed that the problem of deciding whether a general graph contains a 4-cycle requires $\Theta(\sqrt{n}/\log n)$ rounds in CONGEST. For counting triangles, the best known algorithm of Chang, Pettie, and Zhang [SODA 2019] takes $\tilde{O}(\sqrt{n})$ rounds. Finally, our result extends to distributed certification. We show that, for every FO formula~$\varphi$, and every graph class of bounded expansion, there exists a certification scheme for $\varphi$ using certificates on $O(\log n)$ bits. This significantly generalizes the recent result of Feuilloley, Bousquet, and Pierron [PODC 2022], which held solely for graphs of bounded treedepth.

Given a graph G=(V,E), a connected Grundy coloring is a proper vertex coloring that can be obtained by a first-fit heuristic on a connected vertex sequence. A first-fit coloring heuristic is one that attributes to each vertex in a sequence the lowest-index color not used for its preceding neighbors. A connected vertex sequence is one in which each element, except for the first one, is connected to at least one element preceding it. The connected Grundy coloring problem consists of obtaining a connected Grundy coloring maximizing the number of colors. In this paper, we propose two integer programming (IP) formulations and a local-search enhanced biased random-key genetic algorithm (BRKGA) for the connected Grundy coloring problem. The first formulation follows the standard way of partitioning the vertices into color classes while the second one relies on the idea of representatives in an attempt to break symmetries. The BRKGA encompasses a local search procedure using a newly proposed neighborhood. A theoretical neighborhood analysis is also presented. Extensive computational experiments indicate that the problem is computationally demanding for the proposed IP formulations. Nonetheless, the formulation by representatives outperforms the standard one for the considered benchmark instances. Additionally, our BRKGA can find high-quality solutions in low computational times for considerably large instances, showing improved performance when enhanced with local search and a reset mechanism. Moreover we show that our BRKGA can be easily extended to successfully tackle the Grundy coloring problem, i.e., the one without the connectivity requirements.

In the work [$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs, SIAM J. Comput. 24(3), 411--439, (1995)], Wen-Lian Hsu claims three results concerning the class of circular-arc graphs: - the design of so-called \emph{decomposition trees} that represent the structure of all normalized intersection models of circular-arc graphs, - an $\mathcal{O}(m\cdot n)$ recognition algorithm for circular-arc graphs, - an $\mathcal{O}(m\cdot n)$ isomorphism algorithm for circular-arc graphs. In [Discrete Math. Theor. Comput. Sci., 15(1), 157--182, 2013] Curtis, Lin, McConnell, Nussbaum, Soulignac, Spinrad, and Szwarcfiter showed that Hsu's isomorphism algorithm is incorrect. In this note, we show that the other two results -- namely, the construction of decomposition trees and the recognition algorithm -- are also flawed., Comment: Comment on doi:10.1137/S0097539793260726

Circular-arc graphs are the intersection graphs of arcs of a circle. The main result of this work describes the structure of all \emph{normalized intersection models} of circular-arc graphs. Normalized models of a circular-arc graph reflect the neighborhood relation between its vertices and can be seen as its canonical representations; in particular, any intersection model can be made normalized by possibly extending some of its arcs. We~devise a data-structure, called \emph{PQM-tree}, that maintains the set of all normalized models of a circular-arc graph. We show that the PQM-tree of a circular-arc graph can be computed in linear time. Finally, basing on PQM-trees, we provide a linear-time algorithm for the canonization and the isomorphism problem for circular-arc graphs. We describe the structure of the normalized models of circular-arc graphs using an approach proposed by Hsu~[\emph{SIAM J. Comput. 24(3), 411--439, (1995)}]. In the aforementioned work, Hsu claimed the construction of decomposition trees representing the set of all normalized intersection models of circular-arc graphs and an $\mathcal{O}(nm)$ time isomorphism algorithm for this class of graphs. However, the counterexample given in~[\emph{Discrete Math. Theor. Comput. Sci., 15(1), 157--182, 2013}] shows that Hsu's isomorphism algorithm is incorrect. Also, in a companion paper we show that the decomposition trees proposed by Hsu are not constructed correctly; in particular, we showed that there are circular-arc graphs whose all normalized models do not follow the description given by Hsu., Comment: 84 pages

We introduce and analyze a natural game formulated as follows. In this one-person game, the player is given a random permutation $A=(a_1,\dots, a_n)$ of a multiset $M$ of $n$ reals that sum up to $0$, where each of the $n!$ permutation sequences is equally likely. The player only knows the value of $n$ beforehand. The elements of the sequence are revealed one by one and the player can stop the game at any time. Once the process stops, say, after the $i$th element is revealed, the player collects the amount $\sum_{j=i+1}^{n} a_j$ as his/her payoff and the game is over (the payoff corresponds to the unrevealed part of the sequence). Three online algorithms are given for maximizing the expected payoff in the binary case when $M$ contains only $1$'s and $-1$'s. $\texttt{Algorithm 1}$ is slightly suboptimal, but is easier to analyze. Moreover, it can also be used when $n$ is only known with some approximation. $\texttt{Algorithm 2}$ is exactly optimal but not so easy to analyze on its own. $\texttt{Algorithm 3}$ is the simplest of all three. It turns out that the expected payoffs of the player are $\Theta(\sqrt{n})$ for all three algorithms. In the end, we address the general problem and deal with an arbitrary zero-sum multiset, for which we show that our $\texttt{Algorithm 3}$ returns a payoff proportional to $\sqrt{n}$, which is worst case-optimal., Comment: 10+1 pages, 2 figures

We study stationary online bipartite matching, where both types of nodes--offline and online--arrive according to Poisson processes. Offline nodes wait to be matched for some random time, determined by an exponential distribution, while online nodes need to be matched immediately. This model captures scenarios such as deceased organ donation and time-sensitive task assignments, where there is an inflow of patients and workers (offline nodes) with limited patience, while organs and tasks (online nodes) must be assigned upon arrival. We present an efficient online algorithm that achieves a $(1-1/e+\delta)$-approximation to the optimal online policy's reward for a constant $\delta > 0$, simplifying and improving previous work by Aouad and Sarita\c{c} (2022). Our solution combines recent online matching techniques, particularly pivotal sampling, which enables correlated rounding of tighter linear programming approximations, and a greedy-like algorithm. A key technical component is the analysis of a stochastic process that exploits subtle correlations between offline nodes, using renewal theory. A byproduct of our result is an improvement to the best-known competitive ratio--that compares an algorithm's performance to the optimal offline policy--via a $(1-1/\sqrt{e} + \eta)$-competitive algorithm for a universal constant $\eta > 0$, advancing the results of Patel and Wajc (2024).

We present a computational formulation for the approximate version of several variational inequality problems, investigating their computational complexity and establishing PPAD-completeness. Examining applications in computational game theory, we specifically focus on two key concepts: resilient Nash equilibrium, and multi-leader-follower games -- domains traditionally known for the absence of general solutions. In the presence of standard assumptions and relaxation techniques, we formulate problem versions for such games that are expressible in terms of variational inequalities, ultimately leading to proofs of PPAD-completeness.

HEMS optimization for RTPVs with BESS: impact on costs and temporal resolution, Comment: Journal Batteries

Efficient learning from streaming data is important for modern data analysis due to the continuous and rapid evolution of data streams. Despite significant advancements in stream pattern mining, challenges persist, particularly in managing complex data streams like sequential and weighted itemsets. While reservoir sampling serves as a fundamental method for randomly selecting fixed-size samples from data streams, its application to such complex patterns remains largely unexplored. In this study, we introduce an approach that harnesses a weighted reservoir to facilitate direct pattern sampling from streaming batch data, thus ensuring scalability and efficiency. We present a generic algorithm capable of addressing temporal biases and handling various pattern types, including sequential, weighted, and unweighted itemsets. Through comprehensive experiments conducted on real-world datasets, we evaluate the effectiveness of our method, showcasing its ability to construct accurate incremental online classifiers for sequential data. Our approach not only enables previously unusable online machine learning models for sequential data to achieve accuracy comparable to offline baselines but also represents significant progress in the development of incremental online sequential itemset classifiers., Comment: Accepted at 2024 IEEE International Conference on Big Data

Discovering valuable insights from data through meaningful associations is a crucial task. However, it becomes challenging when trying to identify representative patterns in quantitative databases, especially with large datasets, as enumeration-based strategies struggle due to the vast search space involved. To tackle this challenge, output space sampling methods have emerged as a promising solution thanks to its ability to discover valuable patterns with reduced computational overhead. However, existing sampling methods often encounter limitations when dealing with large quantitative database, resulting in scalability-related challenges. In this work, we propose a novel high utility pattern sampling algorithm and its on-disk version both designed for large quantitative databases based on two original theorems. Our approach ensures both the interactivity required for user-centered methods and strong statistical guarantees through random sampling. Thanks to our method, users can instantly discover relevant and representative utility pattern, facilitating efficient exploration of the database within seconds. To demonstrate the interest of our approach, we present a compelling use case involving archaeological knowledge graph sub-profiles discovery. Experiments on semantic and none-semantic quantitative databases show that our approach outperforms the state-of-the art methods., Comment: Accepted at 2024 IEEE International Conference on Big Data

Conways Game of Life is a cellular automaton noted for its rich, complex, and emergent behavior, which seems qualitatively lifelike it exists within a wider space of different rule-sets of cellular automata none of which have been found to display behaviors that seem as rich as Conways selected example We present here a set of three quantitative tests for lifelike behavior based on the critical brain theory Shannons theory of information entropy and integrated information theory all of which are successfully able to select Conways Game of Life as an outlier within this set which is a nonbiological analogue to the selection of a habitable planet or universe among a wider space of similar settings that cannot support the same kinds of living systems, Comment: 11 pages, 6 figures, IAU conference proceedings

It is shown that $S(G) = O\left(m/\log_2 m + d\right)$ pebbles are sufficient to pebble any DAG $G=(V,E)$, with $m$ edges and maximum in-degree $d$. It was previously known that $S(G) = O\left(d n/\log n\right)$. The result builds on two novel ideas. The first is the notion of $B-budget\ decomposition$ of a DAG $G$, an efficiently computable partition of $G$ into at most $2^{\lfloor \frac{m}{B} \rfloor}$ sub-DAGs, whose cumulative space requirement is at most $B$. The second is the challenging vertices technique, which constructs a pebbling schedule for $G$ from a pebbling schedule for a simplified DAG $G'$, obtained by removing from $G$ a selected set of vertices $W$ and their incident edges. This technique also yields improved pebbling upper bounds for DAGs with bounded genus and for DAGs with bounded topological depth.

In this note, we consider the problem of generating $k$-factorable graphic sequences with connected (resp. no connected) $k$-factors., Comment: 14 pages; 16 figures

The maximum clique problem (MCP) is a fundamental problem in graph theory and in computational complexity. Given a graph G, the problem is that of finding the largest clique (complete subgraph) in G. The MCP has many important applications in different domains and has been much studied. The problem has been shown to be NP-Hard and the corresponding decision problem to be NP-Complete. All exact (optimal) algorithms discovered so far run in exponential time. Various meta-heuristics have been used to approximate the MCP. These include genetic and memetic algorithms, ant colony optimization, greedy algorithms, Tabu algorithms, and simulated annealing. This study presents a critical examination of the effectiveness of applying genetic algorithms (GAs) to the MCP compared to a purely stochastic approach. Our results indicate that Monte Carlo algorithms, which employ random searches to generate and then refine sub-graphs into cliques, often surpass genetic algorithms in both speed and capability, particularly in less dense graphs. This observation challenges the conventional reliance on genetic algorithms, suggesting a reevaluation of the roles of the crossover and mutation operators in exploring the solution space. We observe that, in some of the denser graphs, the recombination strategy of genetic algorithms shows unexpected efficacy, hinting at the untapped potential of genetic methods under specific conditions. This work not only questions established paradigms but also opens avenues for exploring algorithmic efficiency in solving the MCP and other NP-Hard problems, inviting further research into the conditions that favor purely stochastic methods over genetic recombination and vice versa., Comment: 16 pages, 4 fgiures

Given a finite set of red and blue points in $\Rspace^d$, the MST-ratio is defined as the total length of the Euclidean minimum spanning trees of the red points and the blue points, divided by the length of the Euclidean minimum spanning tree of their union. The maximum MST-ratio of a point set is the maximum MST-ratio over all non-trivial colorings of its points by red and blue. We prove that finding the maximum MST-ratio of a given point set is NP-hard when the dimension is part of the input. Moreover, we present a quadratic-time $3$-approximation algorithm for this problem. As part of the proof, we show that, in any metric space, the maximum MST-ratio is smaller than $3$. Additionally, we study the average MST-ratio over all colorings of a set of $n$ points. We show that this average is always at least $\frac{n-2}{n-1}$, and for $n$ random points uniformly distributed in a $d$-dimensional unit cube, the average tends to $\sqrt[d]{2}$ in expectation as $n$ approaches infinity.

The Job Shop Scheduling Problem (JSP) is a pivotal challenge in operations research and is essential for evaluating the effectiveness and performance of scheduling algorithms. Scheduling problems are a crucial domain in combinatorial optimization, where resources (machines) are allocated to job tasks to minimize the completion time (makespan) alongside other objectives like energy consumption. This research delves into the intricacies of JSP, focusing on optimizing performance metrics and minimizing energy consumption while considering various constraints such as deadlines and release dates. Recognizing the multi-dimensional nature of benchmarking in JSP, this study underscores the significance of reference libraries and datasets like JSPLIB in enriching algorithm evaluation. The research highlights the importance of problem instance characteristics, including job and machine numbers, processing times, and machine availability, emphasizing the complexities introduced by energy consumption considerations. An innovative instance configurator is proposed, equipped with parameters such as the number of jobs, machines, tasks, and speeds, alongside distributions for processing times and energy consumption. The generated instances encompass various configurations, reflecting real-world scenarios and operational constraints. These instances facilitate comprehensive benchmarking and evaluation of scheduling algorithms, particularly in contexts of energy efficiency. A comprehensive set of 500 test instances has been generated and made publicly available, promoting further research and benchmarking in JSP. These instances enable robust analyses and foster collaboration in developing advanced, energy-efficient scheduling solutions by providing diverse scenarios., Comment: 26th International Workshop on Configuration (ConfWS 2024)

The study of domination in graphs has led to a variety of domination problems studied in the literature. Most of these follow the following general framework: Given a graph $G$ and an integer $k$, decide if there is a set $S$ of $k$ vertices such that (1) some inner property $\phi(S)$ (e.g., connectedness) is satisfied, and (2) each vertex $v$ satisfies some domination property $\rho(S, v)$ (e.g., there is an $s\in S$ that is adjacent to $v$). Since many real-world graphs are sparse, we seek to determine the optimal running time of such problems in both the number $n$ of vertices and the number $m$ of edges in $G$. While the classic dominating set problem admits a rather limited improvement in sparse graphs (Fischer, K\"unnemann, Redzic SODA'24), we show that natural variants studied in the literature admit much larger speed-ups, with a diverse set of possible running times. Specifically, we obtain conditionally optimal algorithms for: 1) $r$-Multiple $k$-Dominating Set (each vertex must be adjacent to at least $r$ vertices in $S$): If $r\le k-2$, we obtain a running time of $(m/n)^{r} n^{k-r+o(1)}$ that is conditionally optimal assuming the 3-uniform hyperclique hypothesis. In sparse graphs, this fully interpolates between $n^{k-1\pm o(1)}$ and $n^{2\pm o(1)}$, depending on $r$. Curiously, when $r=k-1$, we obtain a randomized algorithm beating $(m/n)^{k-1} n^{1+o(1)}$ and we show that this algorithm is close to optimal under the $k$-clique hypothesis. 2) $H$-Dominating Set ($S$ must induce a pattern $H$). We conditionally settle the complexity of three such problems: (a) Dominating Clique ($H$ is a $k$-clique), (b) Maximal Independent Set of size $k$ ($H$ is an independent set on $k$ vertices), (c) Dominating Induced Matching ($H$ is a perfect matching on $k$ vertices).

The macroscopic model for a neutron star (NS) as a liquid drop at the equilibrium is used to extend the Tolman-Oppenheimer-Volkoff (TOV) equations taking into account the gradient terms responsible for the system surface. The parameters of the Schwarzschild metric in the spherical case are found with these surface corrections in the leading (zero) order of the leptodermic approximation $a/R<<1$, where $a$ is the NS effective-surface (ES) thickness, and $R$ is the effective NS radius. The energy density $\mathcal{E}$ is considered in a general form including the functions of the particle number density and of its gradient terms. The macroscopic gravitational potential $\Phi(\rho)$ is taken into account in the simplest form as expansion in powers of $\rho-\overline{\rho} $, where $\overline{\rho}$ is the saturation density, up to second order, in terms of its contributions to th separation particle energy and incompressibility. Density distributions $\rho$ across the NS ES in the normal direction to the ES, which are derived in the simple analytical form at the same leading approximation, was used for the derivation of the modified TOV (MTOV) equations by accounting for their NS surface corrections. The MTOV equations are analytically solved at first order and the results are compared with the standard TOV approach of the zero order., Comment: 24 pages, 9 figures, 1 table. arXiv admin note: text overlap with arXiv:2403.01445

Bourgain's symmetrization theorem is a powerful technique reducing boolean analysis on product spaces to the cube. It states that for any product $\Omega_i^{\otimes d}$, function $f: \Omega_i^{\otimes d} \to \mathbb{R}$, and $q > 1$: $$||T_{\frac{1}{2}}f(x)||_q \leq ||\tilde{f}(r,x)||_{q} \leq ||T_{c_q}f(x)||_q$$ where $T_{\rho}f = \sum\limits \rho^Sf^{=S}$ is the noise operator and $\widetilde{f}(r,x) = \sum\limits r_Sf^{=S}(x)$ `symmetrizes' $f$ by convolving its Fourier components $\{f^{=S}\}_{S \subseteq [d]}$ with a random boolean string $r \in \{\pm 1\}^d$. In this work, we extend the symmetrization theorem to high dimensional expanders (HDX). Adapting work of O'Donnell and Zhao (2021), we give as a corollary a proof of optimal global hypercontractivity for partite HDX, resolving one of the main open questions of Gur, Lifshitz, and Liu (STOC 2022). Adapting work of Bourgain (JAMS 1999), we also give the first booster theorem for HDX, resolving a main open questions of Bafna, Hopkins, Kaufman, and Lovett (STOC 2022). Our proof is based on two elementary new ideas in the theory of high dimensional expansion. First we introduce `$q$-norm HDX', generalizing standard spectral notions to higher moments, and observe every spectral HDX is a $q$-norm HDX. Second, we introduce a simple method of coordinate-wise analysis on HDX which breaks high dimensional random walks into coordinate-wise components, and allows each component to be analyzed as a $1$-dimensional operator locally within $X$. This allows for application of standard tricks such as the replacement method, greatly simplifying prior analytic techniques.

The use of Fermat-Torricelli points can be an effective mathematical tool for analyzing numerical series that have a large variance, a pronounced nonlinear trend, or do not have a normal distribution of a random variable. Linear dependencies are very rare in nature. Smoothing numerical series by constructing Fermat-Torricelli points reduces the influence of the random component on the final result. The presence of a normal distribution of a random variable for numerical series that relate to long time intervals is an exception to the rule rather than an axiom. The external environment (international economic relations, scientific and technological progress, political events) is constantly changing, which in turn, in general, does not give grounds to assert that under these conditions a random variable satisfies the requirements of the Gauss-Markov theorem., Comment: 14 pages , 3 figures

The paper considers implementations of some randomized algorithms in connection with obtaining a random $n^2 \times n^2$ Sudoku matrix with programming language C++. For this purpose we describes the set $\Pi_n$ of all $(2n) \times n$ matrices, consisting of elements of the set $\mathbb{Z}_n =\{ 1,2,\ldots ,n\}$, such that every row is a permutation. We emphasize the relationship between these matrices and the $n^2 \times n^2$ Sudoku matrices. An algorithm to obtain random $\Pi_n$ matrices is presented in this paper. Several auxiliary algorithms that are related to the underlying problem have been described. We evaluated all algorithms according to two criteria - probability evaluation, and time for generation of random objects and checking of belonging to a specific set. This evaluations are interesting from both theoretical and practical point of view because they are particularly useful in the analysis of computer programs., Comment: 14 pages. arXiv admin note: substantial text overlap with arXiv:1312.0192

This paper responds to a commentary by Neal (2024) regarding the Distinctiveness centrality metrics introduced by Fronzetti Colladon and Naldi (2020). Distinctiveness centrality offers a novel reinterpretation of degree centrality, particularly emphasizing the significance of direct connections to loosely connected peers within (social) networks. This response paper presents a more comprehensive analysis of the correlation between Distinctiveness and the Beta and Gamma measures. All five distinctiveness measures are considered, as well as a more meaningful range of the alpha parameter and different network topologies, distinguishing between weighted and unweighted networks. Findings indicate significant variability in correlations, supporting the viability of Distinctiveness as alternative or complementary metrics within social network analysis. Moreover, the paper presents computational complexity analysis and simplified R code for practical implementation. Encouraging initial findings suggest potential applications in diverse domains, inviting further exploration and comparative analyses.

Maintenance decisions range from the simple detection of faults to ultimately predicting future failures and solving the problem. These traditionally human decisions are nowadays increasingly supported by data and the ultimate aim is to make them autonomous. This paper explores the challenges encountered in data driven maintenance, and proposes to consider four aspects in a maturity framework: data / decision maturity, the translation from the real world to data, the computability of decisions (using models) and the causality in the obtained relations. After a discussion of the theoretical concepts involved, the exploration continues by considering a practical fault detection and identification problem. Two approaches, i.e. experience based and model based, are compared and discussed in terms of the four aspects in the maturity framework. It is observed that both approaches yield the same decisions, but still differ in the assignment of causality. This confirms that a maturity assessment not only concerns the type of decision, but should also include the other proposed aspects., Comment: in Proceedings of the 8th European Conference of the Prognostics and Health Management Society 2024

Coalition formation is a key capability in multi-agent systems. An important problem in coalition formation is coalition structure generation: partitioning agents into coalitions to optimize the social welfare. This is a challenging problem that has been the subject of active research for the past three decades. In this paper, we present a novel algorithm, SMART, for the problem based on a hybridization of three innovative techniques. Two of these techniques are based on dynamic programming, where we show a powerful connection between the coalitions selected for evaluation and the performance of the algorithms. These algorithms use offline phases to optimize the choice of coalitions to evaluate. The third one uses branch-and-bound and integer partition graph search to explore the solution space. Our techniques bring a new way of approaching the problem and a new level of precision to the field. In experiments over several common value distributions, we show that the hybridization of these techniques in SMART is faster than the fastest prior algorithms (ODP-IP, BOSS) in generating optimal solutions across all the value distributions.

Bottom-up role-mining is the determination of a set of roles given as input a set of users and the permissions those users possess. It is well-established in the research literature, and in practice, as an important problem in information security. A natural objective that has been explored in prior work is for the set of roles to be of minimum size. We address this problem for practical inputs while reconciling foundations, specifically, that the problem is \cnph. We first observe that an approach from prior work that exploits a sufficient condition for an efficient algorithm, while a useful first step, does not scale to more recently proposed benchmark inputs. We propose a new technique: the enumeration of maximal bicliques. We point out that the number of maximal bicliques provides a natural measure of the hardness of an input. We leverage the enumeration of maximal bicliques in two different ways. Our first approach addresses more than half the benchmark inputs to yield exact results. The other approach is needed for hard instances; in it, we identify and adopt as roles those that correspond to large maximal bicliques. We have implemented all our algorithms and carried out an extensive empirical assessment, which suggests that our approaches are promising. Our code is available publicly as open-source., Comment: 23 pages, 7 figures, 9 tables

The information-encoding molecules RNA and DNA form a combinatorially large set of secondary structures through nucleic acid base pairing. Thermodynamic prediction algorithms predict favoured, or minimum free energy (MFE), secondary structures, and can assign an equilibrium probability to any structure via the partition function: a Boltzman-weighted sum over the set of secondary structures. MFE is NP-hard in the presence pseudoknots, base pairings that violate a restricted planarity condition. However, unpseudoknotted structures are amenable to dynamic programming: for a single DNA/RNA strand there are polynomial time algorithms for MFE and partition function. For multiple strands, the problem is more complicated due to entropic penalties. Dirks et al [SICOMP Review; 2007] showed that for O(1) strands, with N bases, there is a polynomial time in N partition function algorithm, however their technique did not generalise to MFE which they left open. We give the first polynomial time (O(N^4)) algorithm for unpseudoknotted multiple (O(1)) strand MFE, answering the open problem from Dirks et al. The challenge lies in considering rotational symmetry of secondary structures, a feature not immediately amenable to dynamic programming algorithms. Our proof has two main technical contributions: First, a polynomial upper bound on the number of symmetric secondary structures to be considered when computing rotational symmetry penalties. Second, that bound is leveraged by a backtracking algorithm to find the MFE in an exponential space of contenders. Our MFE algorithm has the same asymptotic run time as Dirks et al's partition function algorithm, suggesting efficient handling of rotational symmetry, although higher space complexity. It also seems reasonably tight in the number of strands since Codon, Hajiaghayi & Thachuk [DNA27, 2021] have shown that unpseudoknotted MFE is NP-hard for O(N) strands., Comment: 35 pages, 4 figures, 3 appendices

We study the multi-party randomized communication complexity of computing a fair allocation of $m$ indivisible goods to $n < m$ equally entitled agents. We first consider MMS allocations, allocations that give every agent at least her maximin share. Such allocations are guaranteed to exist for simple classes of valuation functions. We consider the expected number of bits that each agent needs to transmit, on average over all agents. For unit demand valuations, we show that this number is only $O(1)$ (but $\Theta(\log n)$, if one seeks EF1 allocations instead of MMS allocations), for binary additive valuations we show that it is $\Theta(\log \frac{m}{n})$, and for 2-valued additive valuations we show a lower bound of $\Omega(\frac{m}{n})$. For general additive valuations, MMS allocations need not exist. We consider a notion of {\em approximately proportional} (Aprop) allocations, that approximates proportional allocations in two different senses, being both Prop1 (proportional up to one item), and $\frac{n}{2n-1}$-TPS (getting at least a $\frac{n}{2n-1}$ fraction of the {\em truncated proportional share}, and hence also at least a $\frac{n}{2n-1}$ fraction of the MMS). We design randomized protocols that output Aprop allocations, in which the expected average number of bits transmitted per agent is $O(\log m)$. For the stronger notion of MXS ({\em minimum EFX share}) we show a lower bound of $\Omega(\frac{m}{n})$.

In this paper, we study the outerplanarity of planar graphs, i.e., the number of times that we must (in a planar embedding that we can initially freely choose) remove the outerface vertices until the graph is empty. It is well-known that there are $n$-vertex graphs with outerplanarity $\tfrac{n}{6}+\Theta(1)$, and not difficult to show that the outerplanarity can never be bigger. We give here improved bounds of the form $\tfrac{n}{2g}+2g+O(1)$, where $g$ is the fence-girth, i.e., the length of the shortest cycle with vertices on both sides. This parameter $g$ is at least the connectivity of the graph, and often bigger; for example, our results imply that planar bipartite graphs have outerplanarity $\tfrac{n}{8}+O(1)$. We also show that the outerplanarity of a planar graph $G$ is at most $\tfrac{1}{2}$diam$(G)+O(\sqrt{n})$, where diam$(G)$ is the diameter of the graph. All our bounds are tight up to smaller-order terms, and a planar embedding that achieves the outerplanarity bound can be found in linear time.

Given a set \emph{S} of spatial feature types, its feature instances, a study area, and a neighbor relationship, the goal is to find pairs $<$a region ($r_{g}$), a subset \emph{C} of \emph{S}$>$ such that \emph{C} is a statistically significant regional-colocation pattern in $r_{g}$. This problem is important for applications in various domains including ecology, economics, and sociology. The problem is computationally challenging due to the exponential number of regional colocation patterns and candidate regions. Previously, we proposed a miner \cite{10.1145/3557989.3566158} that finds statistically significant regional colocation patterns. However, the numerous simultaneous statistical inferences raise the risk of false discoveries (also known as the multiple comparisons problem) and carry a high computational cost. We propose a novel algorithm, namely, multiple comparisons regional colocation miner (MultComp-RCM) which uses a Bonferroni correction. Theoretical analysis, experimental evaluation, and case study results show that the proposed method reduces both the false discovery rate and computational cost.

Finding a simple path of even length between two designated vertices in a directed graph is a fundamental NP-complete problem known as the EvenPath problem. Nedev proved in 1999, that for directed planar graphs, the problem can be solved in polynomial time. More than two decades since then, we make the first progress in extending the tractable classes of graphs for this problem. We give a polynomial time algorithm to solve the EvenPath problem for classes of H-minor-free directed graphs,1 where H is a single-crossing graph. We make two new technical contributions along the way, that might be of independent interest. The first, and perhaps our main, contribution is the construction of small, planar, parity-mimicking networks. These are graphs that mimic parities of all possible paths between a designated set of terminals of the original graph. Finding vertex disjoint paths between given source-destination pairs of vertices is another fundamental problem, known to be NP-complete in directed graphs, though known to be tractable in planar directed graphs. We encounter a natural variant of this problem, that of finding disjoint paths between given pairs of vertices, but with constraints on parity of the total length of paths. The other significant contribution of our paper is to give a polynomial time algorithm for the 3-disjoint paths with total parity problem, in directed planar graphs with some restrictions (and also in directed graphs of bounded treewidth).

We focus on designing Peer-to-Peer (P2P) networks that enable efficient communication. Over the last two decades, there has been substantial algorithmic research on distributed protocols for building P2P networks with various desirable properties such as high expansion, low diameter, and robustness to a large number of deletions. A key underlying theme in all of these works is to distributively build a \emph{random graph} topology that guarantees the above properties. Moreover, the random connectivity topology is widely deployed in many P2P systems today, including those that implement blockchains and cryptocurrencies. However, a major drawback of using a random graph topology for a P2P network is that the random topology does not respect the \emph{underlying} (Internet) communication topology. This creates a large \emph{propagation delay}, which is a major communication bottleneck in modern P2P networks. In this paper, we work towards designing P2P networks that are communication-efficient (having small propagation delay) with provable guarantees. Our main contribution is an efficient, decentralized protocol, $\textsc{Close-Weaver}$, that transforms a random graph topology embedded in an underlying Euclidean space into a topology that also respects the underlying metric. We then present efficient point-to-point routing and broadcast protocols that achieve essentially optimal performance with respect to the underlying space., Comment: 33 pages, 7 figures, full version of paper to appear in ESA 2024

We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. An example is the absentminded driver game, as well as team games in which the members have limited communication capabilities. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings across three different solution concepts: Nash, multiselves based on evidential decision theory (EDT), and multiselves based on causal decision theory (CDT). We are interested in both exact and approximate solution computation. As special cases, we consider (1) single-player games, (2) two-player zero-sum games and relationships to maximin values, and (3) games without exogenous stochasticity (chance nodes). We relate these problems to the complexity classes P, PPAD, PLS, $\Sigma_2^P$ , $\exists$R, and $\exists \forall$R., Comment: Long version of the paper that got accepted to the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI 2024). 35 pages, 10 figures, 1 table

We revisit the input perturbations framework for differential privacy where noise is added to the input $A\in \mathcal{S}$ and the result is then projected back to the space of admissible datasets $\mathcal{S}$. Through this framework, we first design novel efficient algorithms to privately release pair-wise cosine similarities. Second, we derive a novel algorithm to compute $k$-way marginal queries over $n$ features. Prior work could achieve comparable guarantees only for $k$ even. Furthermore, we extend our results to $t$-sparse datasets, where our efficient algorithms yields novel, stronger guarantees whenever $t\le n^{5/6}/\log n\,.$ Finally, we provide a theoretical perspective on why \textit{fast} input perturbation algorithms works well in practice. The key technical ingredients behind our results are tight sum-of-squares certificates upper bounding the Gaussian complexity of sets of solutions., Comment: 21 ppages, ICML 2024

Graph clustering is a central topic in unsupervised learning with a multitude of practical applications. In recent years, multi-view graph clustering has gained a lot of attention for its applicability to real-world instances where one has access to multiple data sources. In this paper we formalize a new family of models, called \textit{multi-view stochastic block models} that captures this setting. For this model, we first study efficient algorithms that naively work on the union of multiple graphs. Then, we introduce a new efficient algorithm that provably outperforms previous approaches by analyzing the structure of each graph separately. Furthermore, we complement our results with an information-theoretic lower bound studying the limits of what can be done in this model. Finally, we corroborate our results with experimental evaluations., Comment: 31 pages, ICML 2024

We consider the semi-random graph model of [Makarychev, Makarychev and Vijayaraghavan, STOC'12], where, given a random bipartite graph with $\alpha$ edges and an unknown bipartition $(A, B)$ of the vertex set, an adversary can add arbitrary edges inside each community and remove arbitrary edges from the cut $(A, B)$ (i.e. all adversarial changes are \textit{monotone} with respect to the bipartition). For this model, a polynomial time algorithm is known to approximate the Balanced Cut problem up to value $O(\alpha)$ [MMV'12] as long as the cut $(A, B)$ has size $\Omega(\alpha)$. However, it consists of slow subroutines requiring optimal solutions for logarithmically many semidefinite programs. We study the fine-grained complexity of the problem and present the first near-linear time algorithm that achieves similar performances to that of [MMV'12]. Our algorithm runs in time $O(|V(G)|^{1+o(1)} + |E(G)|^{1+o(1)})$ and finds a balanced cut of value $O(\alpha)$. Our approach appears easily extendible to related problem, such as Sparsest Cut, and also yields an near-linear time $O(1)$-approximation to Dagupta's objective function for hierarchical clustering [Dasgupta, STOC'16] for the semi-random hierarchical stochastic block model inputs of [Cohen-Addad, Kanade, Mallmann-Trenn, Mathieu, JACM'19]., Comment: 24 pages, ICML 2024

Although the known maximum total generalized correntropy (MTGC) and generalized maximum blakezisserman total correntropy (GMBZTC) algorithms can maintain good performance under the errors-in-variables (EIV) model disrupted by generalized Gaussian noise, their requirement for manual ad-justment of parameters is excessive, greatly increasing the practical difficulty of use. To solve this problem, the total arctangent based on logical distance metric (TACLDM) algo-rithm is proposed by utilizing the advantage of few parameters in logical distance metric (LDM) theory and the convergence behavior is improved by the arctangent function. Compared with other competing algorithms, the TACLDM algorithm not only has fewer parameters, but also has better robustness to generalized Gaussian noise and significantly reduces the steady-state error. Furthermore, the analysis of the algorithm in the generalized Gaussian noise environment is analyzed in detail in this paper. Finally, computer simulations demonstrate the outstanding performance of the TACLDM algorithm and the rigorous theoretical deduction in this paper., Comment: 10 page

It is possible to improve upon Tunstall coding using a collection of multiple parse trees. The best such results so far are Iwata and Yamamoto's maximum cost AIVF codes. The most efficient algorithm for designing such codes is an iterative one that could run in exponential time. In this paper, we show that this problem fits into the framework of a newly developed technique that uses linear programming with the Ellipsoid method to solve the minimum cost Markov chain problem. This permits constructing maximum cost AIVF codes in (weakly) polynomial time., Comment: Expanded version of paper appearing on ISIT 2024

As supercomputers' complexity has grown, the traditional boundaries between processor, memory, network, and accelerators have blurred, making a homogeneous computer model, in which the overall computer system is modeled as a continuous medium with homogeneously distributed computational power, memory, and data movement transfer capabilities, an intriguing and powerful abstraction. By applying a homogeneous computer model to algorithms with a given I/O complexity, we recover from first principles, other discrete computer models, such as the roofline model, parallel computing laws, such as Amdahl's and Gustafson's laws, and phenomenological observations, such as super-linear speedup. One of the homogeneous computer model's distinctive advantages is the capability of directly linking the performance limits of an application to the physical properties of a classical computer system. Applying the homogeneous computer model to supercomputers, such as Frontier, Fugaku, and the Nvidia DGX GH200, shows that applications, such as Conjugate Gradient (CG) and Fast Fourier Transforms (FFT), are rapidly approaching the fundamental classical computational limits, where the performance of even denser systems in terms of compute and memory are fundamentally limited by the speed of light., Comment: 10 pages, 8 figures, 3 tables

We study the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of $k$ robots to their destinations with the aim of minimizing the total energy (i.e., the total length traveled). We develop novel techniques to push beyond previously-established results that were restricted to solid grids. We design a fixed-parameter additive approximation algorithm for this problem parameterized by $k$ alone. This result, which is of independent interest, allows us to prove the following two results pertaining to well-studied coordinated motion planning problems: (1) A fixed-parameter algorithm, parameterized by $k$, for routing a single robot to its destination while avoiding the other robots, which is related to the famous Rush-Hour Puzzle; and (2) a fixed-parameter algorithm, parameterized by $k$ plus the treewidth of the input graph, for the standard \textsc{Coordinated Motion Planning} (CMP) problem in which we need to route all the $k$ robots to their destinations. The latter of these results implies, among others, the fixed-parameter tractability of CMP parameterized by $k$ on graphs of bounded outerplanarity, which include bounded-height subgrids. We complement the above results with a lower bound which rules out the fixed-parameter tractability for CMP when parameterized by the total energy. This contrasts the recently-obtained tractability of the problem on solid grids under the same parameterization. As our final result, we strengthen the aforementioned fixed-parameter tractability to hold not only on solid grids but all graphs of bounded local treewidth -- a class including, among others, all graphs of bounded genus.

A book embedding of a graph is a drawing that maps vertices onto a line and edges to simple pairwise non-crossing curves drawn into pages, which are half-planes bounded by that line. Two-page book embeddings, i.e., book embeddings into 2 pages, are of special importance as they are both NP-hard to compute and have specific applications. We obtain a 2^(O(\sqrt{n})) algorithm for computing a book embedding of an n-vertex graph on two pages -- a result which is asymptotically tight under the Exponential Time Hypothesis. As a key tool in our approach, we obtain a single-exponential fixed-parameter algorithm for the same problem when parameterized by the treewidth of the input graph. We conclude by establishing the fixed-parameter tractability of computing minimum-page book embeddings when parameterized by the feedback edge number, settling an open question arising from previous work on the problem., Comment: An extended abstract of this paper has been accepted at ICALP 2024

The classical 3SUM conjecture states that the class of 3SUM-hard problems does not admit a truly subquadratic $O(n^{2-\delta})$-time algorithm, where $\delta >0$, in classical computing. The geometric 3SUM-hard problems have widely been studied in computational geometry and recently, these problems have been examined under the quantum computing model. For example, Ambainis and Larka [TQC'20] designed a quantum algorithm that can solve many geometric 3SUM-hard problems in $O(n^{1+o(1)})$-time, whereas Buhrman [ITCS'22] investigated lower bounds under quantum 3SUM conjecture that claims there does not exist any sublinear $O(n^{1-\delta})$-time quantum algorithm for the 3SUM problem. The main idea of Ambainis and Larka is to formulate a 3SUM-hard problem as a search problem, where one needs to find a point with a certain property over a set of regions determined by a line arrangement in the plane. The quantum speed-up then comes from the application of the well-known quantum search technique called Grover search over all regions. This paper further generalizes the technique of Ambainis and Larka for some 3SUM-hard problems when a solution may not necessarily correspond to a single point or the search regions do not immediately correspond to the subdivision determined by a line arrangement. Given a set of $n$ points and a positive number $q$, we design $O(n^{1+o(1)})$-time quantum algorithms to determine whether there exists a triangle among these points with an area at most $q$ or a unit disk that contains at least $q$ points. We also give an $O(n^{1+o(1)})$-time quantum algorithm to determine whether a given set of intervals can be translated so that it becomes contained in another set of given intervals and discuss further generalizations.

The cross dock door design problem consists of deciding on the number and capacity of inbound and outbound doors for receiving product pallets from origin nodes and exiting them to destination nodes. The uncertainty, realized in scenarios, lies in the occurrence of these nodes, the number and cost of the pallets, and the disruption of the capacity of the doors. It is represented using a stochastic two stage binary quadratic model. The first stage decisions are related to the cross dock infrastructure design, and the second stage decisions are related to the node to assignments of the doors. This is the first time, as far as we know, that a stochastic two stage binary quadratic model has been presented for minimizing the construction cost of the infrastructure and its exploitation expected cost in the scenarios. Given the difficulty of solving this combinatorial problem, a mathematically equivalent mixed integer linear formulation is introduced. However, searching an optimal solution is still impractical for commercial solvers. Thus, a scenario cluster decomposition based matheuristic algorithm is introduced to obtain feasible solutions with small optimality gap and reasonable computational effort. A broad study to validate the proposal gives solutions with a much smaller gap than the ones provided by a state of the art general solver. In fact, the proposal provides solutions with a 1 to 5% optimality gap, while the solver does it with up to a 12% gap, if any, and requires a wall time two orders of magnitude higher., Comment: 20 pages, 5 figures

In his 2018 paper, Herlihy introduced an atomic protocol for multi-party asset swaps across different blockchains. His model represents an asset swap by a directed graph whose nodes are the participating parties and edges represent asset transfers, and rational behavior of the participants is captured by a preference relation between a protocol's outcomes. Asset transfers between parties are achieved using smart contracts. These smart contracts are quite involved and they require storage and processing of a large number of paths in the swap digraph, limiting practical significance of his protocol. His paper also describes a different protocol that uses only standard hash time-lock contracts (HTLC's), but this simpler protocol applies only to some special types of digraphs. He left open the question whether there is a simple and efficient protocol for cross-chain asset swaps in arbitrary digraphs. Motivated by this open problem, we conducted a comprehensive study of \emph{HTLC-based protocols}, in which all asset transfers are implemented with HTLCs. Our main contribution is a full characterization of swap digraphs that have such protocols.

Simplets, constituting elementary units within simplicial complexes (SCs), serve as foundational elements for the structural analysis of SCs. Previous efforts have focused on the exact count or approximation of simplet count rather than their frequencies, with the latter being more practical in large-scale SCs. This paper enables simplet frequency analysis of SCs by introducing the Simplet Frequency Distribution (SFD) vector. In addition, we present a bound on the sample complexity required for accurately approximating the SFD vector by any uniform sampling-based algorithm. We also present a simple algorithm for this purpose and justify the theoretical bounds with experiments on some random simplicial complexes., Comment: EuroCG2024

Maximal Extractable Value (MEV) has emerged as a new frontier in the design of blockchain systems. In this paper, we propose making the MEV extraction rate as part of the protocol design space. Our aim is to leverage this parameter to maintain a healthy balance between block producers (who need to be compensated) and users (who need to feel encouraged to transact). We follow the approach introduced by EIP-1559 and design a similar mechanism to dynamically update the MEV extraction rate with the goal of stabilizing it at a target value. We study the properties of this dynamic mechanism and show that, while convergence to the target can be guaranteed for certain parameters, instability, and even chaos, can occur in other cases. Despite these complexities, under general conditions, the system concentrates in a neighborhood of the target equilibrium implying high long-term performance. Our work establishes, the first to our knowledge, dynamic framework for the integral problem of MEV sharing between extractors and users., Comment: Extended abstract in the 23rd International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2024)