Thank you to arXiv for use of its open access interoperability.
Note: the date of arXiv entries announced right after publication holidays might incorrectly show up as the date of the publication holiday itself. This is due to our ad hoc method of inferring announcement dates, which are not returned by the arXiv API.
Both the antiferromagnetic Ising model and the hard-core model could be said to be tractable on line graphs of bounded degree. For example, Glauber dynamics is rapidly mixing in both cases. In the case of the hard-core model, we know that tractability extends further, to claw-free graphs and somewhat beyond. In contrast, it is shown here that the corresponding extensions are not possible in the case of the antiferromagnetic Ising model.
Both the antiferromagnetic Ising model and the hard-core model could be said to be tractable on line graphs of bounded degree. For example, Glauber dynamics is rapidly mixing in both cases. In the case of the hard-core model, we know that tractability extends further, to claw-free graphs and somewhat beyond. In contrast, it is shown here that the corresponding extensions are not possible in the case of the antiferromagnetic Ising model.
The intersection of two context-free languages is not generally context-free, but no geometric criterion has characterized when it remains so. The crossing gap (max(i'-i, j'-j) for two crossing push-pop arcs) is the natural candidate. We refute this: we exhibit CFLs whose intersection is CFL despite unbounded-gap crossings. The governing quantity is the inner segment measure: for crossing arcs inducing a decomposition w = P1 P2 P3 P4, it is max(|P2|,|P3|), the length of the longer inner segment between interleaved crossing endpoints. We prove a dichotomy for this measure: bounded inner segments imply context-freeness via a finite buffer construction; growing inner segments with pump-sensitive linkages imply non-context-freeness. The inner segment concept applies to all CFL intersections; the strictness of the resulting characterization depends on the language class. For block-counting CFLs (languages requiring equality among designated pairs of block lengths), the dichotomy is complete: the intersection is CFL if and only if the combined arcs are jointly well-nested. For general CFLs, the CFL direction is unconditional; the non-CFL direction requires pump-sensitive linkages whose necessity is the main open problem, reducing the general CFL intersection problem to a specific property of pump-sensitive decompositions.
The intersection of two context-free languages is not generally context-free, but no geometric criterion has characterized when it remains so. The crossing gap (max(i'-i, j'-j) for two crossing push-pop arcs) is the natural candidate. We refute this: we exhibit CFLs whose intersection is CFL despite unbounded-gap crossings. The governing quantity is the inner segment measure: for crossing arcs inducing a decomposition w = P1 P2 P3 P4, it is max(|P2|,|P3|), the length of the longer inner segment between interleaved crossing endpoints. We prove a dichotomy for this measure: bounded inner segments imply context-freeness via a finite buffer construction; growing inner segments with pump-sensitive linkages imply non-context-freeness. The inner segment concept applies to all CFL intersections; the strictness of the resulting characterization depends on the language class. For block-counting CFLs (languages requiring equality among designated pairs of block lengths), the dichotomy is complete: the intersection is CFL if and only if the combined arcs are jointly well-nested. For general CFLs, the CFL direction is unconditional; the non-CFL direction requires pump-sensitive linkages whose necessity is the main open problem, reducing the general CFL intersection problem to a specific property of pump-sensitive decompositions.
Constraint satisfaction problems are computational problems that naturally appear in many areas of theoretical computer science. One of the central themes is their computational complexity, and in particular the border between polynomial-time tractability and NP-hardness. In this course we introduce the universal-algebraic approach to study the computational complexity of finite-domain CSPs. The course covers in particular the cyclic terms and bounded width theorems. To keep the presentation accessible, we start the course in the tangible setting of directed graphs and graph homomorphism problems.
Constraint satisfaction problems are computational problems that naturally appear in many areas of theoretical computer science. One of the central themes is their computational complexity, and in particular the border between polynomial-time tractability and NP-hardness. In this course we introduce the universal-algebraic approach to study the computational complexity of finite-domain CSPs. The course covers in particular the cyclic terms and bounded width theorems. To keep the presentation accessible, we start the course in the tangible setting of directed graphs and graph homomorphism problems.
We study the decision problem Affine Rank Minimization, denoted ARM(k). The input consists of rational matrices A_1,...,A_q in Q^{m x n} and rational scalars b_1,...,b_q in Q. The question is whether there exists a real matrix X in R^{m x n} such that trace(A_l^T X) = b_l for all l in {1,...,q} and rank(X) <= k. We first prove membership: for every fixed k >= 1, ARM(k) lies in the existential theory of the reals by giving an explicit existential encoding of the rank constraint using a constant-size factorization witness. We then prove existential-theory-of-reals hardness via a polynomial-time many-one reduction from ETR to ARM(k), where the target instance uses only affine equalities together with a single global constraint rank(X) <= k. The reduction compiles an ETR formula into an arithmetic circuit in gate-equality normal form and assigns each circuit quantity to a designated entry of X. Affine semantics (constants, copies, addition, and negation) are enforced by linear constraints, while multiplicative semantics are enforced by constant-size rank-forcing gadgets. Soundness is certified by a fixed-rank gauge submatrix that removes factorization ambiguity. We prove a composition lemma showing that gadgets can be embedded without unintended interactions, yielding global soundness and completeness while preserving polynomial bounds on dimension and bit-length. Consequently, ARM(k) is complete for the existential theory of the reals; in particular, ARM(3) is complete. This shows that feasibility of purely affine constraints under a fixed constant rank bound captures the full expressive power of real algebraic feasibility.
We study the decision problem Affine Rank Minimization, denoted ARM(k). The input consists of rational matrices A_1,...,A_q in Q^{m x n} and rational scalars b_1,...,b_q in Q. The question is whether there exists a real matrix X in R^{m x n} such that trace(A_l^T X) = b_l for all l in {1,...,q} and rank(X) <= k. We first prove membership: for every fixed k >= 1, ARM(k) lies in the existential theory of the reals by giving an explicit existential encoding of the rank constraint using a constant-size factorization witness. We then prove existential-theory-of-reals hardness via a polynomial-time many-one reduction from ETR to ARM(k), where the target instance uses only affine equalities together with a single global constraint rank(X) <= k. The reduction compiles an ETR formula into an arithmetic circuit in gate-equality normal form and assigns each circuit quantity to a designated entry of X. Affine semantics (constants, copies, addition, and negation) are enforced by linear constraints, while multiplicative semantics are enforced by constant-size rank-forcing gadgets. Soundness is certified by a fixed-rank gauge submatrix that removes factorization ambiguity. We prove a composition lemma showing that gadgets can be embedded without unintended interactions, yielding global soundness and completeness while preserving polynomial bounds on dimension and bit-length. Consequently, ARM(k) is complete for the existential theory of the reals; in particular, ARM(3) is complete. This shows that feasibility of purely affine constraints under a fixed constant rank bound captures the full expressive power of real algebraic feasibility.
Deterministic black-box polynomial identity testing (PIT) for read-once oblivious algebraic branching programs (ROABPs) is a central open problem in algebraic complexity, particularly in the absence of variable ordering. Prior deterministic algorithms either rely on order information or incur significant overhead through combinatorial isolation techniques.
In this paper, we introduce an algebraic rigidity framework for ROABPs based on the internal structure of their associated matrix word algebras. We show that nonzero width-$w$ ROABPs induce word algebras whose effective algebraic degrees of freedom collapse to dimension at most $w^2$, independent of the number of variables. This rigidity enables deterministic witness construction via intrinsic algebraic invariants, bypassing rank concentration, isolation lemmas, and probabilistic tools used in previous work.Thus, we obtain the first order-oblivious deterministic black-box PIT algorithm for ROABPs, running in quasi-polynomial time $n\cdot(wd)^{O(w^2)}$. This establishes that algebraic rigidity alone suffices to derandomize PIT in this model, without assuming ordering information.
The framework further isolates a single remaining obstacle to full polynomial-time complexity. We formulate a Modular Stability Conjecture, asserting that width-$w$ ROABPs are stable under hashing into cyclic quotient rings $\mathbb{K}[λ]/< λ^r-1 >$ once the modulus exceeds a polynomial threshold in $w$ and the individual degree. This conjecture arises naturally from the low-dimensional coefficient structure revealed by rigidity and is supported by extensive empirical evidence.
Assuming the conjecture, our methods yield a fully polynomial-time deterministic black-box PIT algorithm for ROABPs, matching the complexity of the best-known white-box algorithms and reducing the black-box problem to a concrete algebraic stability question.
Deterministic black-box polynomial identity testing (PIT) for read-once oblivious algebraic branching programs (ROABPs) is a central open problem in algebraic complexity, particularly in the absence of variable ordering. Prior deterministic algorithms either rely on order information or incur significant overhead through combinatorial isolation techniques.
In this paper, we introduce an algebraic rigidity framework for ROABPs based on the internal structure of their associated matrix word algebras. We show that nonzero width-$w$ ROABPs induce word algebras whose effective algebraic degrees of freedom collapse to dimension at most $w^2$, independent of the number of variables. This rigidity enables deterministic witness construction via intrinsic algebraic invariants, bypassing rank concentration, isolation lemmas, and probabilistic tools used in previous work.Thus, we obtain the first order-oblivious deterministic black-box PIT algorithm for ROABPs, running in quasi-polynomial time $n\cdot(wd)^{O(w^2)}$. This establishes that algebraic rigidity alone suffices to derandomize PIT in this model, without assuming ordering information.
The framework further isolates a single remaining obstacle to full polynomial-time complexity. We formulate a Modular Stability Conjecture, asserting that width-$w$ ROABPs are stable under hashing into cyclic quotient rings $\mathbb{K}[λ]/< λ^r-1 >$ once the modulus exceeds a polynomial threshold in $w$ and the individual degree. This conjecture arises naturally from the low-dimensional coefficient structure revealed by rigidity and is supported by extensive empirical evidence.
Assuming the conjecture, our methods yield a fully polynomial-time deterministic black-box PIT algorithm for ROABPs, matching the complexity of the best-known white-box algorithms and reducing the black-box problem to a concrete algebraic stability question.
Kinematics of mechanisms is intricately coupled to their geometry and their utility often arises out of the ability to perform reproducible motion with fewer actuating degrees of freedom. In this article, we explore the assembly of scissor-units, each made of two rigid linear members connected by a pin joint. The assembly has a single degree of freedom, where actuating any single unit results in a shape change of the entire assembly. We derive expressions for the effective curvature of the unit and the trajectory of the mechanism's tip as a function of the geometric variables which we then use as the basis to program two tasks in the mechanism: shape morphing and writing. By phrasing these tasks as optimization problems and utilizing the differentiable simulation framework, we arrive at solutions that are then tested in table-top experiments. Our results show that the geometry of scissor assemblies can be leveraged for automated navigation and inspection in complex domains, in light of the optimization framework. However, we highlight that the challenges associated with rapid programming and error-free implementation in experiments without feedback still remain.
Kinematics of mechanisms is intricately coupled to their geometry and their utility often arises out of the ability to perform reproducible motion with fewer actuating degrees of freedom. In this article, we explore the assembly of scissor-units, each made of two rigid linear members connected by a pin joint. The assembly has a single degree of freedom, where actuating any single unit results in a shape change of the entire assembly. We derive expressions for the effective curvature of the unit and the trajectory of the mechanism's tip as a function of the geometric variables which we then use as the basis to program two tasks in the mechanism: shape morphing and writing. By phrasing these tasks as optimization problems and utilizing the differentiable simulation framework, we arrive at solutions that are then tested in table-top experiments. Our results show that the geometry of scissor assemblies can be leveraged for automated navigation and inspection in complex domains, in light of the optimization framework. However, we highlight that the challenges associated with rapid programming and error-free implementation in experiments without feedback still remain.
Quantifying the degree of dissimilarity between two probability distributions on a finite metric space is a fundamental task in Computer Science and Computer Vision. A natural dissimilarity measure based on optimal transport is the Earth Mover's Distance (EMD). A key technique for analyzing this metric, pioneered by Charikar (2002) and Indyk and Thaper (2003), involves constructing low-distortion embeddings of EMD(X) into the Lebesgue space $L_1$.
It became a key problem to investigate whether the upper bound of $O(\log n)$ can be improved for important classes of metric spaces known to admit low-distortion embeddings into $L_1$. In the context of Computer Vision, grid graphs, especially planar grids, are among the most fundamental. Indyk posed the related problem of estimating the $L_1$-distortion of the space of uniform distributions on $n$-point subsets of $R^2$. The Progress Report, last updated in August 2011, highlighted two key results: first, the work of Khot and Naor (2006) on Hamming cubes, which showed that the $L_1$-distortion for Hamming cubes meets the described above upper estimate, and second, the result of Naor and Schechtman (2007) for planar grids, which established that the $L_1$-distortion of for a planar $n$ by $n$ grid is $Ω(\sqrt{\log n})$.
Our first result is the improvement of the lower bound on the $L_1$-distortion for grids to $Ω(\log n)$, matching the universal upper bound up to multiplicative constants. The key ingredient allowing us to obtain these sharp estimates is a new Sobolev-type inequality for scalar-valued functions on the grid graphs. Our method is also applicable to many recursive families of graphs, such as diamond and Laakso graphs. We obtain the sharp distortion estimates of $\log n$ in these cases as well.
Quantifying the degree of dissimilarity between two probability distributions on a finite metric space is a fundamental task in Computer Science and Computer Vision. A natural dissimilarity measure based on optimal transport is the Earth Mover's Distance (EMD). A key technique for analyzing this metric, pioneered by Charikar (2002) and Indyk and Thaper (2003), involves constructing low-distortion embeddings of EMD(X) into the Lebesgue space $L_1$.
It became a key problem to investigate whether the upper bound of $O(\log n)$ can be improved for important classes of metric spaces known to admit low-distortion embeddings into $L_1$. In the context of Computer Vision, grid graphs, especially planar grids, are among the most fundamental. Indyk posed the related problem of estimating the $L_1$-distortion of the space of uniform distributions on $n$-point subsets of $R^2$. The Progress Report, last updated in August 2011, highlighted two key results: first, the work of Khot and Naor (2006) on Hamming cubes, which showed that the $L_1$-distortion for Hamming cubes meets the described above upper estimate, and second, the result of Naor and Schechtman (2007) for planar grids, which established that the $L_1$-distortion of for a planar $n$ by $n$ grid is $Ω(\sqrt{\log n})$.
Our first result is the improvement of the lower bound on the $L_1$-distortion for grids to $Ω(\log n)$, matching the universal upper bound up to multiplicative constants. The key ingredient allowing us to obtain these sharp estimates is a new Sobolev-type inequality for scalar-valued functions on the grid graphs. Our method is also applicable to many recursive families of graphs, such as diamond and Laakso graphs. We obtain the sharp distortion estimates of $\log n$ in these cases as well.
Authors: Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, Yu-Ching Shen
The local Hamiltonian (LH) problem is the canonical $\mathsf{QMA}$-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on $n$ qubits cannot be solved classically in time $O(2^{(1-\varepsilon)n})$ for any $\varepsilon>0$ under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time $O(2^{(1-\varepsilon)n/2})$ for any $\varepsilon>0$ under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved.
Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of $\mathsf{QMA}$ problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in $O(\sqrt{2^n})$ time for an arbitrary $1/\mathrm{poly}(n)$ relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime.
To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a $T$-time quantum circuit acting on $N$ qubits into a $(d+1)$-local Hamiltonian acting on $N+O(T^{1/d})$ qubits. This improves the standard construction based on the unary clock, which uses $N+O(T)$ qubits.
The local Hamiltonian (LH) problem is the canonical $\mathsf{QMA}$-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on $n$ qubits cannot be solved classically in time $O(2^{(1-\varepsilon)n})$ for any $\varepsilon>0$ under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time $O(2^{(1-\varepsilon)n/2})$ for any $\varepsilon>0$ under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved.
Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of $\mathsf{QMA}$ problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in $O(\sqrt{2^n})$ time for an arbitrary $1/\mathrm{poly}(n)$ relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime.
To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a $T$-time quantum circuit acting on $N$ qubits into a $(d+1)$-local Hamiltonian acting on $N+O(T^{1/d})$ qubits. This improves the standard construction based on the unary clock, which uses $N+O(T)$ qubits.
We present the first polynomial-time algorithm for computing a near-optimal \emph{flow}-expander decomposition. Given a graph $G$ and a parameter $φ$, our algorithm removes at most a $φ\log^{1+o(1)}n$ fraction of edges so that every remaining connected component is a $φ$-\emph{flow}-expander (a stronger guarantee than being a $φ$-\emph{cut}-expander). This achieves overhead $\log^{1+o(1)}n$, nearly matching the $Ω(\log n)$ graph-theoretic lower bound that already holds for cut-expander decompositions, up to a $\log^{o(1)}n$ factor. Prior polynomial-time algorithms required removing $O(φ\log^{1.5}n)$ and $O(φ\log^{2}n)$ fractions of edges to guarantee $φ$-cut-expander and $φ$-flow-expander components, respectively.
We present the first polynomial-time algorithm for computing a near-optimal \emph{flow}-expander decomposition. Given a graph $G$ and a parameter $φ$, our algorithm removes at most a $φ\log^{1+o(1)}n$ fraction of edges so that every remaining connected component is a $φ$-\emph{flow}-expander (a stronger guarantee than being a $φ$-\emph{cut}-expander). This achieves overhead $\log^{1+o(1)}n$, nearly matching the $Ω(\log n)$ graph-theoretic lower bound that already holds for cut-expander decompositions, up to a $\log^{o(1)}n$ factor. Prior polynomial-time algorithms required removing $O(φ\log^{1.5}n)$ and $O(φ\log^{2}n)$ fractions of edges to guarantee $φ$-cut-expander and $φ$-flow-expander components, respectively.
Challenge the Champ is a simple tournament format, where an ordering of the players -- called a seeding -- is decided. The first player in this order is the initial champ, and faces the next player. The outcome of each match decides the current champion, who faces the next player in the order. Each player also has a popularity, and the value of each match is the popularity of the winner. Value maximization in tournaments has been previously studied when each match has a deterministic outcome. However, match outcomes are often probabilistic, rather than deterministic. We study robust value maximization in Challenge the Champ tournaments, when the winner of a match may be probabilistic. That is, we seek to maximize the total value that is obtained, irrespective of the outcome of probabilistic matches. We show that even in simple binary settings, for non-adaptive algorithms, the optimal robust value -- which we term the \textsc{VnaR}, or the value not at risk -- is hard to approximate. However, if we allow adaptive algorithms that determine the order of challengers based on the outcomes of previous matches, or restrict the matches with probabilistic outcomes, we can obtain good approximations to the optimal \textsc{VnaR}.
Challenge the Champ is a simple tournament format, where an ordering of the players -- called a seeding -- is decided. The first player in this order is the initial champ, and faces the next player. The outcome of each match decides the current champion, who faces the next player in the order. Each player also has a popularity, and the value of each match is the popularity of the winner. Value maximization in tournaments has been previously studied when each match has a deterministic outcome. However, match outcomes are often probabilistic, rather than deterministic. We study robust value maximization in Challenge the Champ tournaments, when the winner of a match may be probabilistic. That is, we seek to maximize the total value that is obtained, irrespective of the outcome of probabilistic matches. We show that even in simple binary settings, for non-adaptive algorithms, the optimal robust value -- which we term the \textsc{VnaR}, or the value not at risk -- is hard to approximate. However, if we allow adaptive algorithms that determine the order of challengers based on the outcomes of previous matches, or restrict the matches with probabilistic outcomes, we can obtain good approximations to the optimal \textsc{VnaR}.
Given an undirected graph G and a set A \subseteq V(G), an A-path is a path in G that starts and ends at two distinct vertices of A with intermediate vertices in V(G) \setminus A. An A-path is called an (A,\ell)-path if the length of the path is exactly \ell. In the {\sc (A, \ell)-Path Packing} problem (ALPP), we seek to determine whether there exist k vertex-disjoint (A, \ell)-paths in G or not. We pursue this problem with respect to structural parameters. We prove that ALPP is W[1]-hard when it is parameterized by the combined parameter distance to path (dtp) and |A|. In addition, we consider the combined parameters distance to cluster (cvd) + |A| and distance to cluster (cvd) + \ell. For both these combined parameters, we provide FPT algorithms. Finally, we consider the vertex cover number (vc) as the parameter and provide a kernel with O(vc^2) vertices.
Given an undirected graph G and a set A \subseteq V(G), an A-path is a path in G that starts and ends at two distinct vertices of A with intermediate vertices in V(G) \setminus A. An A-path is called an (A,\ell)-path if the length of the path is exactly \ell. In the {\sc (A, \ell)-Path Packing} problem (ALPP), we seek to determine whether there exist k vertex-disjoint (A, \ell)-paths in G or not. We pursue this problem with respect to structural parameters. We prove that ALPP is W[1]-hard when it is parameterized by the combined parameter distance to path (dtp) and |A|. In addition, we consider the combined parameters distance to cluster (cvd) + |A| and distance to cluster (cvd) + \ell. For both these combined parameters, we provide FPT algorithms. Finally, we consider the vertex cover number (vc) as the parameter and provide a kernel with O(vc^2) vertices.
Authors: Antoine Amarilli, Sven Dziadek, Luc Segoufin
For a fixed regular language $L$, the enumeration of $L$-infixes is the following task: we are given an input word $w = a_1 \cdots a_n$ and we must enumerate the infixes of $w$ that belong to $L$, i.e., the pairs $i \leq j$ such that $a_i \cdots a_j \in L$. We are interested in dynamic enumeration of $L$-infixes, where we must additionally support letter substitution updates on $w$ (e.g., "replace the $i$-th letter of $w$ by a letter $a$"). Each update changes the set of infixes to enumerate, and resets the enumeration state.
We study for which regular languages $L$ we can perform dynamic enumeration of $L$-infixes in constant delay (i.e., the next infix is always produced in constant time) and constant additional memory throughout the enumeration, while supporting each update in constant time.
We show that, for languages $L$ with a neutral letter, if the language $L$ belongs to the class ZG and is extensible (i.e., if $u \in L$ and $u$ is a factor of $v$ then $v \in L$), then dynamic enumeration of $L$-infixes can be achieved with a simple algorithm that ensures constant-time updates and constant delay, but not constant additional memory. Our main contribution is then to show an algorithm that additionally uses only constant additional memory, and applies to a more general class of semi-extensible ZG languages for which we give several equivalent characterizations. We further discuss whether our results can be generalized to larger language classes and show some (conditional) lower bounds.
For a fixed regular language $L$, the enumeration of $L$-infixes is the following task: we are given an input word $w = a_1 \cdots a_n$ and we must enumerate the infixes of $w$ that belong to $L$, i.e., the pairs $i \leq j$ such that $a_i \cdots a_j \in L$. We are interested in dynamic enumeration of $L$-infixes, where we must additionally support letter substitution updates on $w$ (e.g., "replace the $i$-th letter of $w$ by a letter $a$"). Each update changes the set of infixes to enumerate, and resets the enumeration state.
We study for which regular languages $L$ we can perform dynamic enumeration of $L$-infixes in constant delay (i.e., the next infix is always produced in constant time) and constant additional memory throughout the enumeration, while supporting each update in constant time.
We show that, for languages $L$ with a neutral letter, if the language $L$ belongs to the class ZG and is extensible (i.e., if $u \in L$ and $u$ is a factor of $v$ then $v \in L$), then dynamic enumeration of $L$-infixes can be achieved with a simple algorithm that ensures constant-time updates and constant delay, but not constant additional memory. Our main contribution is then to show an algorithm that additionally uses only constant additional memory, and applies to a more general class of semi-extensible ZG languages for which we give several equivalent characterizations. We further discuss whether our results can be generalized to larger language classes and show some (conditional) lower bounds.
Virtual machine placement is a crucial challenge in cloud computing for efficiently utilizing physical machine resources in data centers. Virtual machine placement can be formulated as a MinUsageTime Dynamic Vector Bin Packing (DVBP) problem, aiming to minimize the total usage time of the physical machines. This paper evaluates state-of-the-art MinUsageTime DVBP algorithms in non-clairvoyant, clairvoyant and learning-augmented online settings, where item durations (virtual machine lifetimes) are unknown, known and predicted, respectively. Besides the algorithms taken from the literature, we also develop several new algorithms or enhancements. Empirical experimentation is carried out with real-world datasets of Microsoft Azure. The insights from the experimental results are discussed to explore the structures of algorithms and promising design elements that work well in practice.
Virtual machine placement is a crucial challenge in cloud computing for efficiently utilizing physical machine resources in data centers. Virtual machine placement can be formulated as a MinUsageTime Dynamic Vector Bin Packing (DVBP) problem, aiming to minimize the total usage time of the physical machines. This paper evaluates state-of-the-art MinUsageTime DVBP algorithms in non-clairvoyant, clairvoyant and learning-augmented online settings, where item durations (virtual machine lifetimes) are unknown, known and predicted, respectively. Besides the algorithms taken from the literature, we also develop several new algorithms or enhancements. Empirical experimentation is carried out with real-world datasets of Microsoft Azure. The insights from the experimental results are discussed to explore the structures of algorithms and promising design elements that work well in practice.
Orders with low crossing number, introduced by Welzl, are a fundamental tool in range searching and computational geometry. Recently, they have found important applications in structural graph theory: set systems with linear shatter functions correspond to graph classes with linear neighborhood complexity. For such systems, Welzl's theorem guarantees the existence of orders with only $\mathcal{O}(\log^2 n)$ crossings. A series of works has progressively improved the runtime for computing such orders, from Chazelle and Welzl's original $\mathcal{O}(|U|^3 |\mathcal{F}|)$ bound, through Har-Peled's $\mathcal{O}(|U|^2|\mathcal{F}|)$, to the recent sampling-based methods of Csikós and Mustafa.
We present a randomized algorithm that computes Welzl orders for set systems with linear primal and dual shatter functions in time $\mathcal{O}(\|S\| \log \|S\|)$, where $\|S\| = |U| + \sum_{X \in \mathcal{F}} |X|$ is the size of the canonical input representation. As an application, we compute compact neighborhood covers in graph classes with (near-)linear neighborhood complexity in time \(\mathcal{O}(n \log n)\) and improve the runtime of first-order model checking on monadically stable graph classes from $\mathcal{O}(n^{5+\varepsilon})$ to $\mathcal{O}(n^{3+\varepsilon})$.
Orders with low crossing number, introduced by Welzl, are a fundamental tool in range searching and computational geometry. Recently, they have found important applications in structural graph theory: set systems with linear shatter functions correspond to graph classes with linear neighborhood complexity. For such systems, Welzl's theorem guarantees the existence of orders with only $\mathcal{O}(\log^2 n)$ crossings. A series of works has progressively improved the runtime for computing such orders, from Chazelle and Welzl's original $\mathcal{O}(|U|^3 |\mathcal{F}|)$ bound, through Har-Peled's $\mathcal{O}(|U|^2|\mathcal{F}|)$, to the recent sampling-based methods of Csikós and Mustafa.
We present a randomized algorithm that computes Welzl orders for set systems with linear primal and dual shatter functions in time $\mathcal{O}(\|S\| \log \|S\|)$, where $\|S\| = |U| + \sum_{X \in \mathcal{F}} |X|$ is the size of the canonical input representation. As an application, we compute compact neighborhood covers in graph classes with (near-)linear neighborhood complexity in time \(\mathcal{O}(n \log n)\) and improve the runtime of first-order model checking on monadically stable graph classes from $\mathcal{O}(n^{5+\varepsilon})$ to $\mathcal{O}(n^{3+\varepsilon})$.
Authors: Michelle Döring, Jessica Enright, Laura Larios-Jones, George Skretas
Algorithmic meta-theorems provide an important tool for showing tractability of graph problems on graph classes defined by structural restrictions. While such results are well established for static graphs, corresponding frameworks for temporal graphs are comparatively limited.
In this work, we revisit past applications of logical meta-theorems to temporal graphs and develop an extended unifying logical framework. Our first contribution is the introduction of logical encodings for the parameters vertex-interval-membership (VIM) width and tree-interval-membership (TIM) width, parameters which capture the signature of vertex and component activity over time. Building on this, we extend existing monadic second-order (MSO) meta-theorems for bounded lifetime and temporal degree to the parameters VIM and TIM width, and establish novel first-order (FO) meta-theorems for all four parameters.
Finally, we signpost a modular lexicon of reusable FO and MSO formulas for a broad range of temporal graph problems, and give an example. This lexicon allows new problems to be expressed compositionally and directly yields fixed-parameter tractability results across the four parameters we consider.
Algorithmic meta-theorems provide an important tool for showing tractability of graph problems on graph classes defined by structural restrictions. While such results are well established for static graphs, corresponding frameworks for temporal graphs are comparatively limited.
In this work, we revisit past applications of logical meta-theorems to temporal graphs and develop an extended unifying logical framework. Our first contribution is the introduction of logical encodings for the parameters vertex-interval-membership (VIM) width and tree-interval-membership (TIM) width, parameters which capture the signature of vertex and component activity over time. Building on this, we extend existing monadic second-order (MSO) meta-theorems for bounded lifetime and temporal degree to the parameters VIM and TIM width, and establish novel first-order (FO) meta-theorems for all four parameters.
Finally, we signpost a modular lexicon of reusable FO and MSO formulas for a broad range of temporal graph problems, and give an example. This lexicon allows new problems to be expressed compositionally and directly yields fixed-parameter tractability results across the four parameters we consider.
Pseudo-deterministic algorithms are randomized algorithms that, with high constant probability, output a fixed canonical solution. The study of pseudo-deterministic algorithms for the global minimum cut problem was recently initiated by Agarwala and Varma [ITCS'26], who gave a black-box reduction incurring an $O(\log n \log \log n)$ overhead. We introduce a natural graph-theoretic tie-breaking mechanism that uniquely selects a canonical minimum cut. Using this mechanism, we obtain: (i) A pseudo-deterministic minimum cut algorithm for weighted graphs running in $O(m\log^2 n)$ time, eliminating the $O(\log n \log \log n)$ overhead of prior work and matching existing randomized algorithms. (ii) The first pseudo-deterministic algorithm for maintaining a canonical minimum cut in a fully-dynamic unweighted graph, with $\mathrm{polylog}(n)$ update time and $\tilde{O}(n)$ query time. (iii) Improved pseudo-deterministic algorithms for unweighted graphs in the dynamic streaming and cut-query models of computation, matching the best randomized algorithms.
Pseudo-deterministic algorithms are randomized algorithms that, with high constant probability, output a fixed canonical solution. The study of pseudo-deterministic algorithms for the global minimum cut problem was recently initiated by Agarwala and Varma [ITCS'26], who gave a black-box reduction incurring an $O(\log n \log \log n)$ overhead. We introduce a natural graph-theoretic tie-breaking mechanism that uniquely selects a canonical minimum cut. Using this mechanism, we obtain: (i) A pseudo-deterministic minimum cut algorithm for weighted graphs running in $O(m\log^2 n)$ time, eliminating the $O(\log n \log \log n)$ overhead of prior work and matching existing randomized algorithms. (ii) The first pseudo-deterministic algorithm for maintaining a canonical minimum cut in a fully-dynamic unweighted graph, with $\mathrm{polylog}(n)$ update time and $\tilde{O}(n)$ query time. (iii) Improved pseudo-deterministic algorithms for unweighted graphs in the dynamic streaming and cut-query models of computation, matching the best randomized algorithms.
We study two log-concave sampling problems: constrained sampling and composite sampling. First, we consider sampling from a target distribution with density proportional to $\exp(-f(x))$ supported on a convex set $K \subset \mathbb{R}^d$, where $f$ is convex. The main challenge is enforcing feasibility without degrading mixing. Using an epigraph transformation, we reduce this task to sampling from a nearly uniform distribution over a lifted convex set in $\mathbb{R}^{d+1}$. We then solve the lifted problem using a proximal sampler. Assuming only a separation oracle for $K$ and a subgradient oracle for $f$, we develop an implementation of the proximal sampler based on the cutting-plane method and rejection sampling. Unlike existing constrained samplers that rely on projection, reflection, barrier functions, or mirror maps, our approach enforces feasibility using only minimal oracle access, resulting in a practical and unbiased sampler without knowing the geometry of the constraint set.
Second, we study composite sampling, where the target is proportional to $\exp(-f(x)-h(x))$ with closed and convex $f$ and $h$. This composite structure is standard in Bayesian inference with $f$ modeling data fidelity and $h$ encoding prior information. We reduce composite sampling via an epigraph lifting of $h$ to constrained sampling in $\mathbb{R}^{d+1}$, which allows direct application of the constrained sampling algorithm developed in the first part. This reduction results in a double epigraph lifting formulation in $\mathbb{R}^{d+2}$, on which we apply a proximal sampler. By keeping $f$ and $h$ separate, we further demonstrate how different combinations of oracle access (such as subgradient and proximal) can be leveraged to construct separation oracles for the lifted problem. For both sampling problems, we establish mixing time bounds measured in Rényi and $χ^2$ divergences.
We study two log-concave sampling problems: constrained sampling and composite sampling. First, we consider sampling from a target distribution with density proportional to $\exp(-f(x))$ supported on a convex set $K \subset \mathbb{R}^d$, where $f$ is convex. The main challenge is enforcing feasibility without degrading mixing. Using an epigraph transformation, we reduce this task to sampling from a nearly uniform distribution over a lifted convex set in $\mathbb{R}^{d+1}$. We then solve the lifted problem using a proximal sampler. Assuming only a separation oracle for $K$ and a subgradient oracle for $f$, we develop an implementation of the proximal sampler based on the cutting-plane method and rejection sampling. Unlike existing constrained samplers that rely on projection, reflection, barrier functions, or mirror maps, our approach enforces feasibility using only minimal oracle access, resulting in a practical and unbiased sampler without knowing the geometry of the constraint set.
Second, we study composite sampling, where the target is proportional to $\exp(-f(x)-h(x))$ with closed and convex $f$ and $h$. This composite structure is standard in Bayesian inference with $f$ modeling data fidelity and $h$ encoding prior information. We reduce composite sampling via an epigraph lifting of $h$ to constrained sampling in $\mathbb{R}^{d+1}$, which allows direct application of the constrained sampling algorithm developed in the first part. This reduction results in a double epigraph lifting formulation in $\mathbb{R}^{d+2}$, on which we apply a proximal sampler. By keeping $f$ and $h$ separate, we further demonstrate how different combinations of oracle access (such as subgradient and proximal) can be leveraged to construct separation oracles for the lifted problem. For both sampling problems, we establish mixing time bounds measured in Rényi and $χ^2$ divergences.
Authors: Hideo Bannai, Yuto Fujie, Peaker Guo, Shunsuke Inenaga, Yuto Nakashima, Simon J. Puglisi, Cristian Urbina
We study the impact that string reversal can have on several repetitiveness measures. First, we exhibit an infinite family of strings where the number, $r$, of runs in the run-length encoding of the Burrows--Wheeler transform (BWT) can increase additively by $Θ(n)$ when reversing the string. This substantially improves the known $Ω(\log n)$ lower-bound for the additive sensitivity of $r$ and it is asymptotically tight. We generalize our result to other variants of the BWT, including the variant with an appended end-of-string symbol and the bijective BWT. We show that an analogous result holds for the size $z$ of the Lempel--Ziv 77 (LZ) parsing of the text, and also for some of its variants, including the non-overlapping LZ parsing, and the LZ-end parsing. Moreover, we describe a family of strings for which the ratio $z(w^R)/z(w)$ approaches $3$ from below as $|w|\rightarrow \infty$. We also show an asymptotically tight lower-bound of $Θ(n)$ for the additive sensitivity of the size $v$ of the smallest lexicographic parsing to string reversal. Finally, we show that the multiplicative sensitivity of $v$ to reversing the string is $Θ(\log n)$, and this lower-bound is also tight. Overall, our results expose the limitations of repetitiveness measures that are widely used in practice, against string reversal -- a simple and natural data transformation.
We study the impact that string reversal can have on several repetitiveness measures. First, we exhibit an infinite family of strings where the number, $r$, of runs in the run-length encoding of the Burrows--Wheeler transform (BWT) can increase additively by $Θ(n)$ when reversing the string. This substantially improves the known $Ω(\log n)$ lower-bound for the additive sensitivity of $r$ and it is asymptotically tight. We generalize our result to other variants of the BWT, including the variant with an appended end-of-string symbol and the bijective BWT. We show that an analogous result holds for the size $z$ of the Lempel--Ziv 77 (LZ) parsing of the text, and also for some of its variants, including the non-overlapping LZ parsing, and the LZ-end parsing. Moreover, we describe a family of strings for which the ratio $z(w^R)/z(w)$ approaches $3$ from below as $|w|\rightarrow \infty$. We also show an asymptotically tight lower-bound of $Θ(n)$ for the additive sensitivity of the size $v$ of the smallest lexicographic parsing to string reversal. Finally, we show that the multiplicative sensitivity of $v$ to reversing the string is $Θ(\log n)$, and this lower-bound is also tight. Overall, our results expose the limitations of repetitiveness measures that are widely used in practice, against string reversal -- a simple and natural data transformation.
Authors: Fan Chen, Sinho Chewi, Constantinos Daskalakis, Alexander Rakhlin
We show that high-accuracy guarantees for log-concave sampling -- that is, iteration and query complexities which scale as $\mathrm{poly}\log(1/δ)$, where $δ$ is the desired target accuracy -- are achievable using stochastic gradients with subexponential tails. Notably, this exhibits a separation with the problem of convex optimization, where stochasticity (even additive Gaussian noise) in the gradient oracle incurs $\mathrm{poly}(1/δ)$ queries. We also give an information-theoretic argument that light-tailed stochastic gradients are necessary for high accuracy: for example, in the bounded variance case, we show that the minimax-optimal query complexity scales as $Θ(1/δ)$. Our framework also provides similar high accuracy guarantees under stochastic zeroth order (value) queries.
We show that high-accuracy guarantees for log-concave sampling -- that is, iteration and query complexities which scale as $\mathrm{poly}\log(1/δ)$, where $δ$ is the desired target accuracy -- are achievable using stochastic gradients with subexponential tails. Notably, this exhibits a separation with the problem of convex optimization, where stochasticity (even additive Gaussian noise) in the gradient oracle incurs $\mathrm{poly}(1/δ)$ queries. We also give an information-theoretic argument that light-tailed stochastic gradients are necessary for high accuracy: for example, in the bounded variance case, we show that the minimax-optimal query complexity scales as $Θ(1/δ)$. Our framework also provides similar high accuracy guarantees under stochastic zeroth order (value) queries.
We study the problem of estimating the size of the maximum matching in the sublinear-time setting. This problem has been extensively studied, with several known upper and lower bounds. A notable result by Behnezhad (FOCS 2021) established a 2-approximation in ~O(n) time.
However, all known upper and lower bounds are in the adaptive query model, where each query can depend on previous answers. In contrast, non-adaptive query models-where the distribution over all queries must be fixed in advance-are widely studied in property testing, often revealing fundamental gaps between adaptive and non-adaptive complexities. This raises the natural question: is adaptivity also necessary for approximating the maximum matching size in sublinear time? This motivates the goal of achieving a constant or even a polylogarithmic approximation using ~O(n) non-adaptive adjacency list queries, similar to what was done by Behnezhad using adaptive queries.
We show that this is not possible by proving that any randomized non-adaptive algorithm achieving an n^{1/3 - gamma}-approximation, for any constant gamma > 0, with probability at least 2/3, must make Omega(n^{1 + eps}) adjacency list queries, for some constant eps > 0 depending on gamma. This result highlights the necessity of adaptivity in achieving strong approximations. However, non-trivial upper bounds are still achievable: we present a simple randomized algorithm that achieves an n^{1/2}-approximation in O(n log^2 n) queries.
Moreover, our lower bound also extends to the newly defined variant of the non-adaptive model, where queries are issued according to a fixed query tree, introduced by Azarmehr, Behnezhad, Ghafari, and Sudan (FOCS 2025) in the context of Local Computation Algorithms.
We study the problem of estimating the size of the maximum matching in the sublinear-time setting. This problem has been extensively studied, with several known upper and lower bounds. A notable result by Behnezhad (FOCS 2021) established a 2-approximation in ~O(n) time.
However, all known upper and lower bounds are in the adaptive query model, where each query can depend on previous answers. In contrast, non-adaptive query models-where the distribution over all queries must be fixed in advance-are widely studied in property testing, often revealing fundamental gaps between adaptive and non-adaptive complexities. This raises the natural question: is adaptivity also necessary for approximating the maximum matching size in sublinear time? This motivates the goal of achieving a constant or even a polylogarithmic approximation using ~O(n) non-adaptive adjacency list queries, similar to what was done by Behnezhad using adaptive queries.
We show that this is not possible by proving that any randomized non-adaptive algorithm achieving an n^{1/3 - gamma}-approximation, for any constant gamma > 0, with probability at least 2/3, must make Omega(n^{1 + eps}) adjacency list queries, for some constant eps > 0 depending on gamma. This result highlights the necessity of adaptivity in achieving strong approximations. However, non-trivial upper bounds are still achievable: we present a simple randomized algorithm that achieves an n^{1/2}-approximation in O(n log^2 n) queries.
Moreover, our lower bound also extends to the newly defined variant of the non-adaptive model, where queries are issued according to a fixed query tree, introduced by Azarmehr, Behnezhad, Ghafari, and Sudan (FOCS 2025) in the context of Local Computation Algorithms.
Authors: Alexandra Henzinger, Edward Pyne, Seyoon Ragavan
We give new algorithms for tree evaluation (S. Cook et al. TOCT 2012) in the catalytic-computing model (Buhrman et al. STOC 2014). Two existing approaches aim to solve tree evaluation (TreeEval) in low space: on the one hand, J. Cook and Mertz (STOC 2024) give an algorithm for TreeEval running in super-logarithmic space $O(\log n\log\log n)$ and super-polynomial time $n^{O(\log\log n)}$. On the other hand, a simple reduction from TreeEval to circuit evaluation, combined with the result of Buhrman et al. (STOC 2014), gives a catalytic algorithm for TreeEval running in logarithmic $O(\log n)$ free space and polynomial time, but with polynomial catalytic space.
We show that the latter result can be improved. We give a catalytic algorithm for TreeEval with logarithmic $O(\log n)$ free space, polynomial runtime, and subpolynomial $2^{\log^εn}$ catalytic space (for any $ε> 0$). Our result gives the first natural problem known to be solvable with logarithmic free space and even $n^{1-ε}$ catalytic space, that is not known to be in standard logspace even under assumptions. Our result immediately implies an improved simulation of time by catalytic space, by the reduction of Williams (STOC 2025).
Our catalytic TreeEval algorithm is inspired by a connection to matching vector families and private information retrieval, and improved constructions of (uniform) matching vector families would imply improvements to our algorithm.
We give new algorithms for tree evaluation (S. Cook et al. TOCT 2012) in the catalytic-computing model (Buhrman et al. STOC 2014). Two existing approaches aim to solve tree evaluation (TreeEval) in low space: on the one hand, J. Cook and Mertz (STOC 2024) give an algorithm for TreeEval running in super-logarithmic space $O(\log n\log\log n)$ and super-polynomial time $n^{O(\log\log n)}$. On the other hand, a simple reduction from TreeEval to circuit evaluation, combined with the result of Buhrman et al. (STOC 2014), gives a catalytic algorithm for TreeEval running in logarithmic $O(\log n)$ free space and polynomial time, but with polynomial catalytic space.
We show that the latter result can be improved. We give a catalytic algorithm for TreeEval with logarithmic $O(\log n)$ free space, polynomial runtime, and subpolynomial $2^{\log^εn}$ catalytic space (for any $ε> 0$). Our result gives the first natural problem known to be solvable with logarithmic free space and even $n^{1-ε}$ catalytic space, that is not known to be in standard logspace even under assumptions. Our result immediately implies an improved simulation of time by catalytic space, by the reduction of Williams (STOC 2025).
Our catalytic TreeEval algorithm is inspired by a connection to matching vector families and private information retrieval, and improved constructions of (uniform) matching vector families would imply improvements to our algorithm.
Authors: Alexander Zhou, Haoyang Li, Anxin Tian, Zhiyuan Li, Yue Wang
On signed social networks, balanced and unbalanced triangles are a critical motif due to their role as the foundations of Structural Balance Theory. The uses for these motifs have been extensively explored in networks with known edge signs, however in the real-world graphs with ground-truth signs are near non-existent, particularly on a large-scale. In reality, edge signs are inferred via various techniques with differing levels of confidence, meaning the edge signs on these graphs should be modelled with a probability value. In this work, we adapt balanced and unbalanced triangles to a setting with uncertain edge signs and explore the problems of triangle counting and enumeration. We provide a baseline and improved method (leveraging the inherent information provided by the edge probabilities in order to reduce the search space) for fast exact counting and enumeration. We also explore approximate solutions for counting via different sampling approaches, including leveraging insights from our improved exact solution to significantly reduce the runtime of each sample resulting in upwards of two magnitudes more queries executed per second. We evaluate the efficiency of all our solutions as well as examine the effectiveness of our sampling approaches on real-world topological networks with a variety of probability distributions.
On signed social networks, balanced and unbalanced triangles are a critical motif due to their role as the foundations of Structural Balance Theory. The uses for these motifs have been extensively explored in networks with known edge signs, however in the real-world graphs with ground-truth signs are near non-existent, particularly on a large-scale. In reality, edge signs are inferred via various techniques with differing levels of confidence, meaning the edge signs on these graphs should be modelled with a probability value. In this work, we adapt balanced and unbalanced triangles to a setting with uncertain edge signs and explore the problems of triangle counting and enumeration. We provide a baseline and improved method (leveraging the inherent information provided by the edge probabilities in order to reduce the search space) for fast exact counting and enumeration. We also explore approximate solutions for counting via different sampling approaches, including leveraging insights from our improved exact solution to significantly reduce the runtime of each sample resulting in upwards of two magnitudes more queries executed per second. We evaluate the efficiency of all our solutions as well as examine the effectiveness of our sampling approaches on real-world topological networks with a variety of probability distributions.
In the {\sc Vertex Multicut} problem the input consists of a graph $G$, integer $k$, and a set $\mathbf{T} = \{(s_1, t_1), \ldots, (s_p, t_p)\}$ of pairs of vertices of $G$. The task is to find a set $X$ of at most $k$ vertices such that, for every $(s_i, t_i) \in \mathbf{T}$, there is no path from $s_i$ to $t_i$ in $G - X$. Marx and Razgon [STOC 2011 and SICOMP 2014] and Bousquet, Daligault, and Thomassé [STOC 2011 and SICOMP 2018] independently and simultaneously gave the first algorithms for {\sc Vertex Multicut} with running time $f(k)n^{O(1)}$. The running time of their algorithms is $2^{O(k^3)}n^{O(1)}$ and $2^{O(k^{O(1)})}n^{O(1)}$, respectively. As part of their result, Marx and Razgon introduce the {\em shadow removal} technique, which was subsequently applied in algorithms for several parameterized cut and separation problems. The shadow removal step is the only step of the algorithm of Marx and Razgon which requires $2^{O(k^3)}n^{O(1)}$ time. Chitnis et al. [TALG 2015] gave an improved version of the shadow removal step, which, among other results, led to a $k^{O(k^2)}n^{O(1)}$ time algorithm for {\sc Vertex Multicut}.
We give a faster algorithm for the {\sc Vertex Multicut} problem with running time $k^{O(k)}n^{O(1)}$. Our main technical contribution is a refined shadow removal step for vertex separation problems that only introduces an overhead of $k^{O(k)}\log n$ time. The new shadow removal step implies a $k^{O(k^2)}n^{O(1)}$ time algorithm for {\sc Directed Subset Feedback Vertex Set} and a $k^{O(k)}n^{O(1)}$ time algorithm for {\sc Directed Multiway Cut}, improving over the previously best known algorithms of Chitnis et al. [TALG 2015].
In the {\sc Vertex Multicut} problem the input consists of a graph $G$, integer $k$, and a set $\mathbf{T} = \{(s_1, t_1), \ldots, (s_p, t_p)\}$ of pairs of vertices of $G$. The task is to find a set $X$ of at most $k$ vertices such that, for every $(s_i, t_i) \in \mathbf{T}$, there is no path from $s_i$ to $t_i$ in $G - X$. Marx and Razgon [STOC 2011 and SICOMP 2014] and Bousquet, Daligault, and Thomassé [STOC 2011 and SICOMP 2018] independently and simultaneously gave the first algorithms for {\sc Vertex Multicut} with running time $f(k)n^{O(1)}$. The running time of their algorithms is $2^{O(k^3)}n^{O(1)}$ and $2^{O(k^{O(1)})}n^{O(1)}$, respectively. As part of their result, Marx and Razgon introduce the {\em shadow removal} technique, which was subsequently applied in algorithms for several parameterized cut and separation problems. The shadow removal step is the only step of the algorithm of Marx and Razgon which requires $2^{O(k^3)}n^{O(1)}$ time. Chitnis et al. [TALG 2015] gave an improved version of the shadow removal step, which, among other results, led to a $k^{O(k^2)}n^{O(1)}$ time algorithm for {\sc Vertex Multicut}.
We give a faster algorithm for the {\sc Vertex Multicut} problem with running time $k^{O(k)}n^{O(1)}$. Our main technical contribution is a refined shadow removal step for vertex separation problems that only introduces an overhead of $k^{O(k)}\log n$ time. The new shadow removal step implies a $k^{O(k^2)}n^{O(1)}$ time algorithm for {\sc Directed Subset Feedback Vertex Set} and a $k^{O(k)}n^{O(1)}$ time algorithm for {\sc Directed Multiway Cut}, improving over the previously best known algorithms of Chitnis et al. [TALG 2015].
We introduce a variant of the multiway cut that we call the min-max connected multiway cut. Given a graph $G=(V,E)$ and a set $Γ\subseteq V$ of $t$ terminals, partition $V$ into $t$ parts such that each part is connected and contains exactly one terminal; the objective is to minimize the maximum weight of the edges leaving any part of the partition. This problem is a natural modification of the standard multiway cut problem and it differs from it in two ways: first, the cost of a partition is defined to be the maximum size of the boundary of any part, as opposed to the sum of all boundaries, and second, the subgraph induced by each part is required to be connected. Although the modified objective function has been considered before in the literature under the name min-max multiway cut, the requirement on each component to be connected has not been studied as far as we know.
We show various hardness results for this problem, including a proof of weak NP-hardness of the weighted version of the problem on graphs with tree-width two, and provide a pseudopolynomial time algorithm as well as an FPTAS for the weighted problem on trees. As a consequence of our investigation we also show that the (unconstrained) min-max multiway cut problem is NP-hard even for three terminals, strengthening the known results.
We introduce a variant of the multiway cut that we call the min-max connected multiway cut. Given a graph $G=(V,E)$ and a set $Γ\subseteq V$ of $t$ terminals, partition $V$ into $t$ parts such that each part is connected and contains exactly one terminal; the objective is to minimize the maximum weight of the edges leaving any part of the partition. This problem is a natural modification of the standard multiway cut problem and it differs from it in two ways: first, the cost of a partition is defined to be the maximum size of the boundary of any part, as opposed to the sum of all boundaries, and second, the subgraph induced by each part is required to be connected. Although the modified objective function has been considered before in the literature under the name min-max multiway cut, the requirement on each component to be connected has not been studied as far as we know.
We show various hardness results for this problem, including a proof of weak NP-hardness of the weighted version of the problem on graphs with tree-width two, and provide a pseudopolynomial time algorithm as well as an FPTAS for the weighted problem on trees. As a consequence of our investigation we also show that the (unconstrained) min-max multiway cut problem is NP-hard even for three terminals, strengthening the known results.
Suppose that we are given a string $s$ of length $n$ over an alphabet $\{0,1,\ldots,n^{O(1)}\}$ and $δ$ is a compression measure for $s$ called string complexity. We describe an index on $s$ with $O(δ\log\frac{n}δ)$ space, measured in $O(\log n)$-bit machine words, that can search in $s$ any string of length $m$ in $O(m + (\mathrm{occ} + 1)\log^εn)$ time, where $\mathrm{occ}$ is the number of found occurrences and $ε> 0$ is any fixed constant (the big-O in the space bound hides factor $\frac{1}ε$). Crucially, the index can be built within this space in $O(n\log n)$ expected time by one left-to-right pass on the string $s$ in a streaming fashion. The index does not use the Karp--Rabin fingerprints, and the randomization in the construction time can be eliminated by using deterministic dictionaries instead of hash tables (with a slowdown). The search time matches currently best results and the space is almost optimal (the known optimum is $O(δ\log\frac{n}{δα})$, where $α= \log_σn$ and $σ$ is the alphabet size, and it coincides with $O(δ\log\frac{n}δ)$ when $δ= O(n / α^2)$). This is the first index that can be constructed within such space and with such time guarantees. To avoid uninteresting marginal cases, all above bounds are stated for $δ\ge Ω(\log\log n)$.
Suppose that we are given a string $s$ of length $n$ over an alphabet $\{0,1,\ldots,n^{O(1)}\}$ and $δ$ is a compression measure for $s$ called string complexity. We describe an index on $s$ with $O(δ\log\frac{n}δ)$ space, measured in $O(\log n)$-bit machine words, that can search in $s$ any string of length $m$ in $O(m + (\mathrm{occ} + 1)\log^εn)$ time, where $\mathrm{occ}$ is the number of found occurrences and $ε> 0$ is any fixed constant (the big-O in the space bound hides factor $\frac{1}ε$). Crucially, the index can be built within this space in $O(n\log n)$ expected time by one left-to-right pass on the string $s$ in a streaming fashion. The index does not use the Karp--Rabin fingerprints, and the randomization in the construction time can be eliminated by using deterministic dictionaries instead of hash tables (with a slowdown). The search time matches currently best results and the space is almost optimal (the known optimum is $O(δ\log\frac{n}{δα})$, where $α= \log_σn$ and $σ$ is the alphabet size, and it coincides with $O(δ\log\frac{n}δ)$ when $δ= O(n / α^2)$). This is the first index that can be constructed within such space and with such time guarantees. To avoid uninteresting marginal cases, all above bounds are stated for $δ\ge Ω(\log\log n)$.
Authors: Tianshuo Zhou, David H. Mathews, Liang Huang
Motivation: RNA design aims to find RNA sequences that fold into a given target secondary structure, a problem also known as RNA inverse folding. However, not all target structures are designable. Recent advances in RNA designability have focused primarily on minimum free energy (MFE)-based criteria, while ensemble-based notions of designability remain largely underexplored. To address this gap, we introduce a theory of ensemble approximation and a probability decomposition framework for bounding the folding probabilities of RNA structures in an explainable way. We further develop a linear-time dynamic programming algorithm that efficiently searches over exponentially many decompositions and identifies the optimal one that yields the tightest probabilistic bound for a given structure. Results: Applying our methods to both native and artificial RNA structures in the ArchiveII and Eterna100 benchmarks, we obtained probability bounds that are much tighter than prior approaches. In addition, our methods further provide anatomical tools for analyzing RNA structures and understanding the sources of design difficulty at the motif level. Availability: Source code and data are available at github.com/shanry/RNA-Undesign. Supplementary information: Supplementary text and data are available in a separate PDF.
Motivation: RNA design aims to find RNA sequences that fold into a given target secondary structure, a problem also known as RNA inverse folding. However, not all target structures are designable. Recent advances in RNA designability have focused primarily on minimum free energy (MFE)-based criteria, while ensemble-based notions of designability remain largely underexplored. To address this gap, we introduce a theory of ensemble approximation and a probability decomposition framework for bounding the folding probabilities of RNA structures in an explainable way. We further develop a linear-time dynamic programming algorithm that efficiently searches over exponentially many decompositions and identifies the optimal one that yields the tightest probabilistic bound for a given structure. Results: Applying our methods to both native and artificial RNA structures in the ArchiveII and Eterna100 benchmarks, we obtained probability bounds that are much tighter than prior approaches. In addition, our methods further provide anatomical tools for analyzing RNA structures and understanding the sources of design difficulty at the motif level. Availability: Source code and data are available at https://github.com/shanry/RNA-Undesign. Supplementary information: Supplementary text and data are available in a separate PDF.
Authors: Brandon Augustino, Dylan Herman, Guneykan Ozgul, Jacob Watkins, Atithi Acharya, Enrico Fontana, Junhyung Lyle Kim, Shouvanik Chakrabarti
Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} yet of great practical importance. Super-quadratic quantum speedups for ILPs have been difficult to obtain because classical algorithms for many-constraint ILPs are global and exhaustive, whereas quantum frameworks that offer super-quadratic speedup exploit local structure of the objective and feasible set. We address this via quantum algorithms for Gomory's group relaxation. The group relaxation of an ILP is obtained by dropping nonnegativity on variables that are positive in the optimal solution of the linear programming (LP) relaxation, while retaining integrality of the decision variables. We present a competitive feasibility-preserving classical local-search algorithm for the group relaxation, and a corresponding quantum algorithm that, under reasonable technical conditions, achieves a super-quadratic speedup. When the group relaxation satisfies a nondegeneracy condition analogous to, but stronger than, LP non-degeneracy, our approach yields the optimal solution to the original ILP. Otherwise, the group relaxation tightens bounds on the optimal objective value of the ILP, and can improve downstream branch-and-cut by reducing the integrality gap; we numerically observe this on several practically relevant ILPs. To achieve these results, we derive efficiently constructible constraint-preserving mixers for the group relaxation with favorable spectral properties, which are of independent interest.
Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} yet of great practical importance. Super-quadratic quantum speedups for ILPs have been difficult to obtain because classical algorithms for many-constraint ILPs are global and exhaustive, whereas quantum frameworks that offer super-quadratic speedup exploit local structure of the objective and feasible set. We address this via quantum algorithms for Gomory's group relaxation. The group relaxation of an ILP is obtained by dropping nonnegativity on variables that are positive in the optimal solution of the linear programming (LP) relaxation, while retaining integrality of the decision variables. We present a competitive feasibility-preserving classical local-search algorithm for the group relaxation, and a corresponding quantum algorithm that, under reasonable technical conditions, achieves a super-quadratic speedup. When the group relaxation satisfies a nondegeneracy condition analogous to, but stronger than, LP non-degeneracy, our approach yields the optimal solution to the original ILP. Otherwise, the group relaxation tightens bounds on the optimal objective value of the ILP, and can improve downstream branch-and-cut by reducing the integrality gap; we numerically observe this on several practically relevant ILPs. To achieve these results, we derive efficiently constructible constraint-preserving mixers for the group relaxation with favorable spectral properties, which are of independent interest.
Authors: Diandre Miguel Sabale, Wolfgang Gatterbauer, Prashant Pandey
Filters are ubiquitous in computer science, enabling space-efficient approximate membership testing. Since Bloom filters were introduced in 1970, decades of work improved their space efficiency and performance. Recently, three new paradigms have emerged offering orders-of-magnitude improvements in false positive rates (FPRs) by using information beyond the input set: (1) learned filters train a model to distinguish (non)members, (2) stacked filters use negative workload samples to build cascading layers, and (3) adaptive filters update internal representation in response to false positive feedback. Yet each paradigm targets specific use cases, introduces complex configuration tuning, and has been evaluated in isolation. This results in unclear trade-offs and a gap in understanding how these approaches compare and when each is most appropriate. This paper presents the first comprehensive evaluation of learned, stacked, and adaptive filters across real-world datasets and query workloads. Our results reveal critical trade-offs: (1) Learned filters achieve up to 10^2 times lower FPRs but exhibit high variance and lack robustness under skewed or dynamic workloads. Critically, model inference overhead leads to up to 10^4 times slower query latencies than stacked or adaptive filters. (2) Stacked filters reliably achieve up to 10^3 times lower FPRs on skewed workloads but require workload knowledge. (3) Adaptive filters are robust across settings, achieving up to 10^3 times lower FPRs under adversarial queries without workload assumptions. Based on our analysis, learned filters suit stable workloads where input features enable effective model training and space constraints are paramount, stacked filters excel when reliable query distributions are known, and adaptive filters are most generalizable, providing robust theoretically bound guarantees even in dynamic or adversarial environments.
Filters are ubiquitous in computer science, enabling space-efficient approximate membership testing. Since Bloom filters were introduced in 1970, decades of work improved their space efficiency and performance. Recently, three new paradigms have emerged offering orders-of-magnitude improvements in false positive rates (FPRs) by using information beyond the input set: (1) learned filters train a model to distinguish (non)members, (2) stacked filters use negative workload samples to build cascading layers, and (3) adaptive filters update internal representation in response to false positive feedback. Yet each paradigm targets specific use cases, introduces complex configuration tuning, and has been evaluated in isolation. This results in unclear trade-offs and a gap in understanding how these approaches compare and when each is most appropriate. This paper presents the first comprehensive evaluation of learned, stacked, and adaptive filters across real-world datasets and query workloads. Our results reveal critical trade-offs: (1) Learned filters achieve up to 10^2 times lower FPRs but exhibit high variance and lack robustness under skewed or dynamic workloads. Critically, model inference overhead leads to up to 10^4 times slower query latencies than stacked or adaptive filters. (2) Stacked filters reliably achieve up to 10^3 times lower FPRs on skewed workloads but require workload knowledge. (3) Adaptive filters are robust across settings, achieving up to 10^3 times lower FPRs under adversarial queries without workload assumptions. Based on our analysis, learned filters suit stable workloads where input features enable effective model training and space constraints are paramount, stacked filters excel when reliable query distributions are known, and adaptive filters are most generalizable, providing robust theoretically bound guarantees even in dynamic or adversarial environments.
The Positional Burrows--Wheeler Transform (PBWT) is a data structure designed for efficiently representing and querying large collections of sequences, such as haplotype panels in genomics. Forward and backward stepping operations -- analogues to LF- and FL-mapping in the traditional BWT -- are fundamental to the PBWT, underpinning many algorithms based on the PBWT for haplotype matching and related analyses. Although the run-length encoded variant of the PBWT (also known as the $μ$-PBWT) achieves $O(\newR)$-word space usage, where $\newR$ is the total number of runs, no data structure supporting both forward and backward stepping in constant time within this space bound was previously known. In this paper, we consider the multi-allelic PBWT that is extended from its original binary form to a general ordered alphabet $\{0, \dots, σ-1\}$. We first establish bounds on the size $\newR$ and then introduce a new $O(\newR)$-word data structure built over a list of haplotypes $\{S_1, \dots, S_\height\}$, each of length $\width$, that supports constant-time forward and backward stepping.
We further revisit two key applications -- haplotype retrieval and prefix search -- leveraging our efficient forward stepping technique. Specifically, we design an $O(\newR)$-word space data structure that supports haplotype retrieval in $O(\log \log_{\word} h + \width)$ time. For prefix search, we present an $O(\height + \newR)$-word data structure that answers queries in $O(m' \log\log_{\word} σ+ \occ)$ time, where $m'$ denotes the length of the longest common prefix returned and $\occ$ denotes the number of haplotypes prefixed the longest prefix.
The Positional Burrows--Wheeler Transform (PBWT) is a data structure designed for efficiently representing and querying large collections of sequences, such as haplotype panels in genomics. Forward and backward stepping operations -- analogues to LF- and FL-mapping in the traditional BWT -- are fundamental to the PBWT, underpinning many algorithms based on the PBWT for haplotype matching and related analyses. Although the run-length encoded variant of the PBWT (also known as the $μ$-PBWT) achieves $O(\newR)$-word space usage, where $\newR$ is the total number of runs, no data structure supporting both forward and backward stepping in constant time within this space bound was previously known. In this paper, we consider the multi-allelic PBWT that is extended from its original binary form to a general ordered alphabet $\{0, \dots, σ-1\}$. We first establish bounds on the size $\newR$ and then introduce a new $O(\newR)$-word data structure built over a list of haplotypes $\{S_1, \dots, S_\height\}$, each of length $\width$, that supports constant-time forward and backward stepping.
We further revisit two key applications -- haplotype retrieval and prefix search -- leveraging our efficient forward stepping technique. Specifically, we design an $O(\newR)$-word space data structure that supports haplotype retrieval in $O(\log \log_{\word} h + \width)$ time. For prefix search, we present an $O(\height + \newR)$-word data structure that answers queries in $O(m' \log\log_{\word} σ+ \occ)$ time, where $m'$ denotes the length of the longest common prefix returned and $\occ$ denotes the number of haplotypes prefixed the longest prefix.
Authors: Michael Xie, Jiayi Wu, Dung Nguyen, Aravind Srinivasan
Differential Privacy is the gold standard in privacy-preserving data analysis. This paper addresses the challenge of producing a differentially edge-private vertex coloring. In this paper, we present two novel algorithms to approach this problem. Both algorithms initially randomly colors each vertex from a fixed size palette, then applies the exponential mechanism to locally resample colors for either all or a chosen subset of the vertices.
Any non-trivial differentially edge private coloring of graph needs to be defective. A coloring of a graph is k defective if all vertices of the graph share it's assigned color with at most k of its neighbors. This is the metric by which we will measure the utility of our algorithms. Our first algorithm applies to d-inductive graphs. Assume we have a d-inductive graph with n vertices and max degree $Δ$. We show that our algorithm provides a \(3ε\)-differentially private coloring with \(O(\frac{\log n}ε+d)\) max defectiveness, given a palette of size $Θ(\fracΔ{\log n}+\frac{1}ε)$ Furthermore, we show that this algorithm can generalize to $O(\fracΔ{cε}+d)$ defectiveness, where c is the size of the palette and $c=O(\fracΔ{\log n})$. Our second algorithm utilizes noisy thresholding to guarantee \(O(\frac{\log n}ε)\) max defectiveness, given a palette of size $Θ(\fracΔ{\log n}+\frac{1}ε)$, generalizing to all graphs rather than just d-inductive ones.
Differential Privacy is the gold standard in privacy-preserving data analysis. This paper addresses the challenge of producing a differentially edge-private vertex coloring. In this paper, we present two novel algorithms to approach this problem. Both algorithms initially randomly colors each vertex from a fixed size palette, then applies the exponential mechanism to locally resample colors for either all or a chosen subset of the vertices.
Any non-trivial differentially edge private coloring of graph needs to be defective. A coloring of a graph is k defective if all vertices of the graph share it's assigned color with at most k of its neighbors. This is the metric by which we will measure the utility of our algorithms. Our first algorithm applies to d-inductive graphs. Assume we have a d-inductive graph with n vertices and max degree $Δ$. We show that our algorithm provides a \(3ε\)-differentially private coloring with \(O(\frac{\log n}ε+d)\) max defectiveness, given a palette of size $Θ(\fracΔ{\log n}+\frac{1}ε)$ Furthermore, we show that this algorithm can generalize to $O(\fracΔ{cε}+d)$ defectiveness, where c is the size of the palette and $c=O(\fracΔ{\log n})$. Our second algorithm utilizes noisy thresholding to guarantee \(O(\frac{\log n}ε)\) max defectiveness, given a palette of size $Θ(\fracΔ{\log n}+\frac{1}ε)$, generalizing to all graphs rather than just d-inductive ones.
June 2-5, 2026 University of Copenhagen sites.google.com/view/wact2026/ Registration deadline: February 28, 2026 Algebraic Complexity Theory investigates the computational complexity of algebraic problems, focusing on arithmetic circuits, polynomial computation, and algebraic models of computation. The goal of this workshop is to present recent advances in the field of algebraic complexity and to highlight the deep underlying … Continue reading 9th Workshop on Algebraic Complexity Theory
By shacharlovett
June 2-5, 2026 University of Copenhagen https://sites.google.com/view/wact2026/ Registration deadline: February 28, 2026 Algebraic Complexity Theory investigates the computational complexity of algebraic problems, focusing on arithmetic circuits, polynomial computation, and algebraic models of computation. The goal of this workshop is to present recent advances in the field of algebraic complexity and to highlight the deep underlying … Continue reading 9th Workshop on Algebraic Complexity Theory
We give new algorithms for tree evaluation (S. Cook et. al. TOCT 2012) in the catalytic-computing model (Buhrman et. al. STOC 2014). Two existing approaches aim to solve tree evaluation in low space: on the one hand, J. Cook and Mertz (STOC 2024) give an algorithm for TreeEval running in super-logarithmic space $O(\log n\log\log n)$ and super-polynomial time $n^{O(\log\log n)}$. On the other hand, a simple reduction from TreeEval to circuit evaluation, combined with the result of Buhrman et al. (STOC 2014), gives a catalytic algorithm for TreeEval running in logarithmic $O(\log n)$ free space and polynomial time, but with polynomial catalytic space.
We show that the latter result can be improved. We give a catalytic algorithm for TreeEval with logarithmic $O(\log n)$ free space, polynomial runtime, and subpolynomial $2^{\log^\epsilon n}$ catalytic space (for any $\epsilon > 0$). Our result opens a new line of attack on putting TreeEval in logspace, and immediately implies an improved simulation of time by catalytic space, by the reduction of Williams (STOC 2025).
Our catalytic TreeEval algorithm is inspired by a connection to matching-vector families and private information retrieval, and improved constructions of (uniform) matching-vector families would imply improvements to our algorithm.
We give new algorithms for tree evaluation (S. Cook et. al. TOCT 2012) in the catalytic-computing model (Buhrman et. al. STOC 2014). Two existing approaches aim to solve tree evaluation in low space: on the one hand, J. Cook and Mertz (STOC 2024) give an algorithm for TreeEval running in super-logarithmic space $O(\log n\log\log n)$ and super-polynomial time $n^{O(\log\log n)}$. On the other hand, a simple reduction from TreeEval to circuit evaluation, combined with the result of Buhrman et al. (STOC 2014), gives a catalytic algorithm for TreeEval running in logarithmic $O(\log n)$ free space and polynomial time, but with polynomial catalytic space.
We show that the latter result can be improved. We give a catalytic algorithm for TreeEval with logarithmic $O(\log n)$ free space, polynomial runtime, and subpolynomial $2^{\log^\epsilon n}$ catalytic space (for any $\epsilon > 0$). Our result opens a new line of attack on putting TreeEval in logspace, and immediately implies an improved simulation of time by catalytic space, by the reduction of Williams (STOC 2025).
Our catalytic TreeEval algorithm is inspired by a connection to matching-vector families and private information retrieval, and improved constructions of (uniform) matching-vector families would imply improvements to our algorithm.
Symmetry of Information (SoI) is a fundamental result in Kolmogorov complexity stating that for all $n$-bit strings $x$ and $y$, $K(x,y) = K(y) + K(x \mid y)$ up to an additive error of $O(\log n)$ [ZL70]. In contrast, understanding whether SoI holds for time-bounded Kolmogorov complexity measures is closely related to longstanding open problems in complexity theory and cryptography, such as the P versus NP question [LW95, Hir22] and the existence of one-way functions [HILNO23, HLO24, HLN24].
In this paper, we prove that SoI fails for $rKt$ complexity, the randomized analogue of Levin's $Kt$ complexity [Lev84]. This is the first unconditional result of this type for a randomized notion of time-bounded Kolmogorov complexity. More generally, we establish a close relationship between the validity of SoI for $rKt$ and the existence of randomized algorithms approximating $rKt(x)$. Motivated by applications in cryptography, we also establish the failure of SoI for a related notion called $pKt$ complexity [HLO24], and provide an extension of the results to the average-case setting. Finally, we prove a near-optimal lower bound on the complexity of estimating conditional $rKt$, a result that might be of independent interest.
Our findings complement those of [Ron04], who demonstrated the failure of SoI for $Kt$ complexity. In contrast, the randomized setting poses a significant challenge, which we overcome using insights from [KK25], structural results about $rKt$ implied by SoI, and techniques from meta-complexity [Oli19] and the theory of computational pseudorandomness [TV07].
Symmetry of Information (SoI) is a fundamental result in Kolmogorov complexity stating that for all $n$-bit strings $x$ and $y$, $K(x,y) = K(y) + K(x \mid y)$ up to an additive error of $O(\log n)$ [ZL70]. In contrast, understanding whether SoI holds for time-bounded Kolmogorov complexity measures is closely related to longstanding open problems in complexity theory and cryptography, such as the P versus NP question [LW95, Hir22] and the existence of one-way functions [HILNO23, HLO24, HLN24].
In this paper, we prove that SoI fails for $rKt$ complexity, the randomized analogue of Levin's $Kt$ complexity [Lev84]. This is the first unconditional result of this type for a randomized notion of time-bounded Kolmogorov complexity. More generally, we establish a close relationship between the validity of SoI for $rKt$ and the existence of randomized algorithms approximating $rKt(x)$. Motivated by applications in cryptography, we also establish the failure of SoI for a related notion called $pKt$ complexity [HLO24], and provide an extension of the results to the average-case setting. Finally, we prove a near-optimal lower bound on the complexity of estimating conditional $rKt$, a result that might be of independent interest.
Our findings complement those of [Ron04], who demonstrated the failure of SoI for $Kt$ complexity. In contrast, the randomized setting poses a significant challenge, which we overcome using insights from [KK25], structural results about $rKt$ implied by SoI, and techniques from meta-complexity [Oli19] and the theory of computational pseudorandomness [TV07].
Fast matrix multiplication algorithms are asymptotically faster than the classical cubic-time algorithm, but they are often slower in practice. One important obstacle is the use of complex coefficients, which increases arithmetic overhead and limits practical efficiency. This paper focuses on transforming complex-coefficient matrix multiplication schemes into equivalent real- or rational-coefficient ones. We present a systematic method that, given a complex-coefficient scheme, either constructs a family of equivalent rational algorithms or proves that no equivalent rational scheme exists. Our approach relies only on basic linear-algebraic properties of similarity transformations of complex matrices. This method recovers the previously known ad hoc results of Dumas, Pernet, and Sedoglavic (2025) and extends them to more general settings, including algorithms involving rational coefficients and square roots, with $i=\sqrt{-1}$ as a special case.
Using this framework, we show that no rational scheme is equivalent to Smirnov's $\langle4,4,9,104\rangle$ $\mathbb{Q}[\sqrt{161}]$ algorithm (2022) and that no real scheme is equivalent to the $\langle4,4,4,48\rangle$ complex algorithm of Kaporin (2024). More generally, our approach can also be used to prove the non-existence of integer-coefficient schemes.
Fast matrix multiplication algorithms are asymptotically faster than the classical cubic-time algorithm, but they are often slower in practice. One important obstacle is the use of complex coefficients, which increases arithmetic overhead and limits practical efficiency. This paper focuses on transforming complex-coefficient matrix multiplication schemes into equivalent real- or rational-coefficient ones. We present a systematic method that, given a complex-coefficient scheme, either constructs a family of equivalent rational algorithms or proves that no equivalent rational scheme exists. Our approach relies only on basic linear-algebraic properties of similarity transformations of complex matrices. This method recovers the previously known ad hoc results of Dumas, Pernet, and Sedoglavic (2025) and extends them to more general settings, including algorithms involving rational coefficients and square roots, with $i=\sqrt{-1}$ as a special case.
Using this framework, we show that no rational scheme is equivalent to Smirnov's $\langle4,4,9,104\rangle$ $\mathbb{Q}[\sqrt{161}]$ algorithm (2022) and that no real scheme is equivalent to the $\langle4,4,4,48\rangle$ complex algorithm of Kaporin (2024). More generally, our approach can also be used to prove the non-existence of integer-coefficient schemes.
Authors: Thomas Boudier, Fabian Kuhn, Augusto Modanese, Ronja Stimpert, Jukka Suomela
We present a complete classification of the distributed computational complexity of local optimization problems in directed cycles for both the deterministic and the randomized LOCAL model. We show that for any local optimization problem $Π$ (that can be of the form min-sum, max-sum, min-max, or max-min, for any local cost or utility function over some finite alphabet), and for any \emph{constant} approximation ratio $α$, the task of finding an $α$-approximation of $Π$ in directed cycles has one of the following complexities:
1. $O(1)$ rounds in deterministic LOCAL, $O(1)$ rounds in randomized LOCAL,
2. $Θ(\log^* n)$ rounds in deterministic LOCAL, $O(1)$ rounds in randomized LOCAL,
3. $Θ(\log^* n)$ rounds in deterministic LOCAL, $Θ(\log^* n)$ rounds in randomized LOCAL,
4. $Θ(n)$ rounds in deterministic LOCAL, $Θ(n)$ rounds in randomized LOCAL.
Moreover, for any given $Π$ and $α$, we can determine the complexity class automatically, with an efficient (centralized, sequential) meta-algorithm, and we can also efficiently synthesize an asymptotically optimal distributed algorithm.
Before this work, similar results were only known for local search problems (e.g., locally checkable labeling problems). The family of local optimization problems is a strict generalization of local search problems, and it contains numerous commonly studied distributed tasks, such as the problems of finding approximations of the maximum independent set, minimum vertex cover, minimum dominating set, and minimum vertex coloring.
We present a complete classification of the distributed computational complexity of local optimization problems in directed cycles for both the deterministic and the randomized LOCAL model. We show that for any local optimization problem $Π$ (that can be of the form min-sum, max-sum, min-max, or max-min, for any local cost or utility function over some finite alphabet), and for any \emph{constant} approximation ratio $α$, the task of finding an $α$-approximation of $Π$ in directed cycles has one of the following complexities:
1. $O(1)$ rounds in deterministic LOCAL, $O(1)$ rounds in randomized LOCAL,
2. $Θ(\log^* n)$ rounds in deterministic LOCAL, $O(1)$ rounds in randomized LOCAL,
3. $Θ(\log^* n)$ rounds in deterministic LOCAL, $Θ(\log^* n)$ rounds in randomized LOCAL,
4. $Θ(n)$ rounds in deterministic LOCAL, $Θ(n)$ rounds in randomized LOCAL.
Moreover, for any given $Π$ and $α$, we can determine the complexity class automatically, with an efficient (centralized, sequential) meta-algorithm, and we can also efficiently synthesize an asymptotically optimal distributed algorithm.
Before this work, similar results were only known for local search problems (e.g., locally checkable labeling problems). The family of local optimization problems is a strict generalization of local search problems, and it contains numerous commonly studied distributed tasks, such as the problems of finding approximations of the maximum independent set, minimum vertex cover, minimum dominating set, and minimum vertex coloring.
$(1^a, 2^b)$-coloring is the problem of partitioning the vertex set of a graph into $a$ independent sets and $b$ 2-independent sets. This problem was recently introduced by Choi and Liu. We study the computational complexity and extremal properties of $(1^a, 2^b)$-coloring. We prove that this problem is NP-Complete even when restricted to certain classes of planar graphs, and we also investigate the extremal values of $b$ when $a$ is fixed and in some $(a + 1)$-colorable classes of graphs. In particular, we prove that $k$-degenerate graphs are $(1^k, 2^{O(\sqrt{n})})$-colorable, that triangle-free planar graphs are $(1^2, 2^{O(\sqrt{n})})$-colorable and that planar graphs are $(1^3, 2^{O(\sqrt{n})})$-colorable. All upper bounds obtained are tight up to a constant factor.
$(1^a, 2^b)$-coloring is the problem of partitioning the vertex set of a graph into $a$ independent sets and $b$ 2-independent sets. This problem was recently introduced by Choi and Liu. We study the computational complexity and extremal properties of $(1^a, 2^b)$-coloring. We prove that this problem is NP-Complete even when restricted to certain classes of planar graphs, and we also investigate the extremal values of $b$ when $a$ is fixed and in some $(a + 1)$-colorable classes of graphs. In particular, we prove that $k$-degenerate graphs are $(1^k, 2^{O(\sqrt{n})})$-colorable, that triangle-free planar graphs are $(1^2, 2^{O(\sqrt{n})})$-colorable and that planar graphs are $(1^3, 2^{O(\sqrt{n})})$-colorable. All upper bounds obtained are tight up to a constant factor.
We present a family of flattening methods of tensors which we call Kronecker-Koszul flattenings, generalizing the famous Koszul flattenings and further equations of secant varieties studied among others by Landsberg, Manivel, Ottaviani and Strassen. We establish new border rank criteria given by vanishing of minors of Kronecker-Koszul flattenings. We obtain the first explicit polynomial equations -- tangency flattenings -- vanishing on secant varieties of Segre variety, but not vanishing on cactus varieties. Additionally, our polynomials have simple determinantal expressions. As another application, we provide a new, computer-free proof that the border rank of the $2\times2$ matrix multiplication tensor is $7$.
We present a family of flattening methods of tensors which we call Kronecker-Koszul flattenings, generalizing the famous Koszul flattenings and further equations of secant varieties studied among others by Landsberg, Manivel, Ottaviani and Strassen. We establish new border rank criteria given by vanishing of minors of Kronecker-Koszul flattenings. We obtain the first explicit polynomial equations -- tangency flattenings -- vanishing on secant varieties of Segre variety, but not vanishing on cactus varieties. Additionally, our polynomials have simple determinantal expressions. As another application, we provide a new, computer-free proof that the border rank of the $2\times2$ matrix multiplication tensor is $7$.
Authors: Christoph Grüne, Berit Johannes, James B. Orlin, Lasse Wulf
Many natural optimization problems derived from $\sf NP$ admit bilevel and multilevel extensions in which decisions are made sequentially by multiple players with conflicting objectives, as in interdiction, adversarial selection, and adjustable robust optimization. Such problems are naturally modeled by alternating quantifiers and, therefore, lie beyond $\sf NP$, typically in the polynomial hierarchy or $\sf PSPACE$. Despite extensive study of these problem classes, relatively few natural completeness results are known at these higher levels. We introduce a general framework for proving completeness in the polynomial hierarchy and $\sf PSPACE$ for problems derived from $\sf NP$. Our approach is based on a refinement of $\sf NP$, which we call $\sf NP$ with solutions ($\sf NP$-$\sf S$), in which solutions are explicit combinatorial objects, together with a restricted class of reductions -- solution-embedding reductions -- that preserve solution structure. We define $\sf NP$-$\sf S$-completeness and show that a large collection of classical $\sf NP$-complete problems, including Clique, Vertex Cover, Knapsack, and Traveling Salesman, are $\sf NP$-$\sf S$-complete.
Using this framework, we establish general meta-theorems showing that if a problem is $\sf NP$-$\sf S$-complete, then its natural two-level extensions are $Σ_2^p$-complete, its three-level extensions are $Σ_3^p$-complete, and its $k$-level extensions are $Σ_k^p$-complete. When the number of levels is unbounded, the resulting problems are $\sf PSPACE$-complete. Our results subsume nearly all previously known completeness results for multilevel optimization problems derived from $\sf NP$ and yield many new ones simultaneously, demonstrating that high computational complexity is a generic feature of multilevel extensions of $\sf NP$-complete problems.
Many natural optimization problems derived from $\sf NP$ admit bilevel and multilevel extensions in which decisions are made sequentially by multiple players with conflicting objectives, as in interdiction, adversarial selection, and adjustable robust optimization. Such problems are naturally modeled by alternating quantifiers and, therefore, lie beyond $\sf NP$, typically in the polynomial hierarchy or $\sf PSPACE$. Despite extensive study of these problem classes, relatively few natural completeness results are known at these higher levels. We introduce a general framework for proving completeness in the polynomial hierarchy and $\sf PSPACE$ for problems derived from $\sf NP$. Our approach is based on a refinement of $\sf NP$, which we call $\sf NP$ with solutions ($\sf NP$-$\sf S$), in which solutions are explicit combinatorial objects, together with a restricted class of reductions -- solution-embedding reductions -- that preserve solution structure. We define $\sf NP$-$\sf S$-completeness and show that a large collection of classical $\sf NP$-complete problems, including Clique, Vertex Cover, Knapsack, and Traveling Salesman, are $\sf NP$-$\sf S$-complete.
Using this framework, we establish general meta-theorems showing that if a problem is $\sf NP$-$\sf S$-complete, then its natural two-level extensions are $Σ_2^p$-complete, its three-level extensions are $Σ_3^p$-complete, and its $k$-level extensions are $Σ_k^p$-complete. When the number of levels is unbounded, the resulting problems are $\sf PSPACE$-complete. Our results subsume nearly all previously known completeness results for multilevel optimization problems derived from $\sf NP$ and yield many new ones simultaneously, demonstrating that high computational complexity is a generic feature of multilevel extensions of $\sf NP$-complete problems.
The kinematics of particles and rigid bodies in the plane are investigated up to higher-order accelerations. Discussion of point trajectories leads from higher-order poles to higher-order Bresse circles of the moving plane. Symplectic geometry in vector space R^2 is used here as a new approach and leads to some new recursive vector formulas. This article is dedicated to the memory of Professor Pennestri.
The kinematics of particles and rigid bodies in the plane are investigated up to higher-order accelerations. Discussion of point trajectories leads from higher-order poles to higher-order Bresse circles of the moving plane. Symplectic geometry in vector space R^2 is used here as a new approach and leads to some new recursive vector formulas. This article is dedicated to the memory of Professor Pennestri.
In the Maximize Phylogenetic Diversity problem, we are given a phylogenetic tree that represents the genetic proximity of species, and we are asked to select a subset of species of maximum phylogenetic diversity to be preserved through conservation efforts, subject to budgetary constraints that allow only k species to be saved. This neglects that it is futile to preserve a predatory species if we do not also preserve at least a subset of the prey it feeds on. Thus, in the Optimizing PD with Dependencies ($ε$-PDD) problem, we are additionally given a food web that represents the predator-prey relationships between species. The goal is to save a set of k species of maximum phylogenetic diversity such that for every saved species, at least one of its prey is also saved. This problem is NP-hard even when the phylogenetic tree is a star. The $α$-PDD problem alters PDD by requiring that at least some fraction $α$ of the prey of every saved species are also saved. In this paper, we study the parameterized complexity of $α$-PDD. We prove that the problem is W[1]-hard and in XP when parameterized by the solution size k, the diversity threshold D, or their complements. When parameterized by the vertex cover number of the food web, $α$-PDD is fixed-parameter tractable (FPT). A key measure of the computational difficulty of a problem that is FPT is the size of the smallest kernel that can be obtained. We prove that, when parameterized by the distance to clique, 1-PDD admits a linear kernel. Our main contribution is to prove that $α$-PDD does not admit a polynomial kernel when parameterized by the vertex cover number plus the diversity threshold D, even if the phylogenetic tree is a star. This implies the non-existence of a polynomial kernel for $α$-PDD also when parameterized by a range of structural parameters of the food web, such as its dist[...]
In the Maximize Phylogenetic Diversity problem, we are given a phylogenetic tree that represents the genetic proximity of species, and we are asked to select a subset of species of maximum phylogenetic diversity to be preserved through conservation efforts, subject to budgetary constraints that allow only k species to be saved. This neglects that it is futile to preserve a predatory species if we do not also preserve at least a subset of the prey it feeds on. Thus, in the Optimizing PD with Dependencies ($ε$-PDD) problem, we are additionally given a food web that represents the predator-prey relationships between species. The goal is to save a set of k species of maximum phylogenetic diversity such that for every saved species, at least one of its prey is also saved. This problem is NP-hard even when the phylogenetic tree is a star. The $α$-PDD problem alters PDD by requiring that at least some fraction $α$ of the prey of every saved species are also saved. In this paper, we study the parameterized complexity of $α$-PDD. We prove that the problem is W[1]-hard and in XP when parameterized by the solution size k, the diversity threshold D, or their complements. When parameterized by the vertex cover number of the food web, $α$-PDD is fixed-parameter tractable (FPT). A key measure of the computational difficulty of a problem that is FPT is the size of the smallest kernel that can be obtained. We prove that, when parameterized by the distance to clique, 1-PDD admits a linear kernel. Our main contribution is to prove that $α$-PDD does not admit a polynomial kernel when parameterized by the vertex cover number plus the diversity threshold D, even if the phylogenetic tree is a star. This implies the non-existence of a polynomial kernel for $α$-PDD also when parameterized by a range of structural parameters of the food web, such as its dist[...]
OMD and its variants give a flexible framework for OCO where the performance depends crucially on the choice of the mirror map. While the geometries underlying OPGD and OEG, both special cases of OMD, are well understood, it remains a challenging open question on how to construct an optimal mirror map for any given constrained set and a general family of loss functions, e.g., sparse losses. Motivated by parameterizing a near-optimal set of mirror maps, we consider a simpler question: is it even possible to obtain polynomial gains in regret by using mirror maps for geometries that interpolate between $L_1$ and $L_2$, which may not be possible by restricting to only OEG ($L_1$) or OPGD ($L_2$).
Our main result answers this question positively. We show that mirror maps based on block norms adapt better to the sparsity of loss functions, compared to previous $L_p$ (for $p \in [1, 2]$) interpolations. In particular, we construct a family of online convex optimization instances in $\mathbb{R}^d$, where block norm-based mirror maps achieve a provable polynomial (in $d$) improvement in regret over OEG and OPGD for sparse loss functions. We then turn to the setting in which the sparsity level of the loss functions is unknown. In this case, the choice of geometry itself becomes an online decision problem. We first show that naively switching between OEG and OPGD can incur linear regret, highlighting the intrinsic difficulty of geometry selection. To overcome this issue, we propose a meta-algorithm based on multiplicative weights that dynamically selects among a family of uniform block norms. We show that this approach effectively tunes OMD to the sparsity of the losses, yielding adaptive regret guarantees. Overall, our results demonstrate that online mirror-map selection can significantly enhance the ability of OMD to exploit sparsity in online convex optimization.
OMD and its variants give a flexible framework for OCO where the performance depends crucially on the choice of the mirror map. While the geometries underlying OPGD and OEG, both special cases of OMD, are well understood, it remains a challenging open question on how to construct an optimal mirror map for any given constrained set and a general family of loss functions, e.g., sparse losses. Motivated by parameterizing a near-optimal set of mirror maps, we consider a simpler question: is it even possible to obtain polynomial gains in regret by using mirror maps for geometries that interpolate between $L_1$ and $L_2$, which may not be possible by restricting to only OEG ($L_1$) or OPGD ($L_2$).
Our main result answers this question positively. We show that mirror maps based on block norms adapt better to the sparsity of loss functions, compared to previous $L_p$ (for $p \in [1, 2]$) interpolations. In particular, we construct a family of online convex optimization instances in $\mathbb{R}^d$, where block norm-based mirror maps achieve a provable polynomial (in $d$) improvement in regret over OEG and OPGD for sparse loss functions. We then turn to the setting in which the sparsity level of the loss functions is unknown. In this case, the choice of geometry itself becomes an online decision problem. We first show that naively switching between OEG and OPGD can incur linear regret, highlighting the intrinsic difficulty of geometry selection. To overcome this issue, we propose a meta-algorithm based on multiplicative weights that dynamically selects among a family of uniform block norms. We show that this approach effectively tunes OMD to the sparsity of the losses, yielding adaptive regret guarantees. Overall, our results demonstrate that online mirror-map selection can significantly enhance the ability of OMD to exploit sparsity in online convex optimization.
Authors: Chendi Qian, Christopher Morris, Stefanie Jegelka, Christian Sohler
There has been a growing interest in using neural networks, especially message-passing neural networks (MPNNs), to solve hard combinatorial optimization problems heuristically. However, existing learning-based approaches for hard combinatorial optimization tasks often rely on supervised training data, reinforcement learning, or gradient estimators, leading to significant computational overhead, unstable training, or a lack of provable performance guarantees. In contrast, classical approximation algorithms offer such performance guarantees under worst-case inputs but are non-differentiable and unable to adaptively exploit structural regularities in natural input distributions. We address this dichotomy with the fundamental example of Uniform Facility Location (UniFL), a variant of the combinatorial facility location problem with applications in clustering, data summarization, logistics, and supply chain design. We develop a fully differentiable MPNN model that embeds approximation-algorithmic principles while avoiding the need for solver supervision or discrete relaxations. Our approach admits provable approximation and size generalization guarantees to much larger instances than seen during training. Empirically, we show that our approach outperforms standard non-learned approximation algorithms in terms of solution quality, closing the gap with computationally intensive integer linear programming approaches. Overall, this work provides a step toward bridging learning-based methods and approximation algorithms for discrete optimization.
There has been a growing interest in using neural networks, especially message-passing neural networks (MPNNs), to solve hard combinatorial optimization problems heuristically. However, existing learning-based approaches for hard combinatorial optimization tasks often rely on supervised training data, reinforcement learning, or gradient estimators, leading to significant computational overhead, unstable training, or a lack of provable performance guarantees. In contrast, classical approximation algorithms offer such performance guarantees under worst-case inputs but are non-differentiable and unable to adaptively exploit structural regularities in natural input distributions. We address this dichotomy with the fundamental example of Uniform Facility Location (UniFL), a variant of the combinatorial facility location problem with applications in clustering, data summarization, logistics, and supply chain design. We develop a fully differentiable MPNN model that embeds approximation-algorithmic principles while avoiding the need for solver supervision or discrete relaxations. Our approach admits provable approximation and size generalization guarantees to much larger instances than seen during training. Empirically, we show that our approach outperforms standard non-learned approximation algorithms in terms of solution quality, closing the gap with computationally intensive integer linear programming approaches. Overall, this work provides a step toward bridging learning-based methods and approximation algorithms for discrete optimization.
Authors: Solveig Wittig, Antonis Vasileiou, Robert R. Nerem, Timo Stoll, Floris Geerts, Yusu Wang, Christopher Morris
In recent years, there has been growing interest in understanding neural architectures' ability to learn to execute discrete algorithms, a line of work often referred to as neural algorithmic reasoning. The goal is to integrate algorithmic reasoning capabilities into larger neural pipelines. Many such architectures are based on (message-passing) graph neural networks (MPNNs), owing to their permutation equivariance and ability to deal with sparsity and variable-sized inputs. However, existing work is either largely empirical and lacks formal guarantees or it focuses solely on expressivity, leaving open the question of when and how such architectures generalize beyond a finite training set. In this work, we propose a general theoretical framework that characterizes the sufficient conditions under which MPNNs can learn an algorithm from a training set of small instances and provably approximate its behavior on inputs of arbitrary size. Our framework applies to a broad class of algorithms, including single-source shortest paths, minimum spanning trees, and general dynamic programming problems, such as the $0$-$1$ knapsack problem. In addition, we establish impossibility results for a wide range of algorithmic tasks, showing that standard MPNNs cannot learn them, and we derive more expressive MPNN-like architectures that overcome these limitations. Finally, we refine our analysis for the Bellman-Ford algorithm, yielding a substantially smaller required training set and significantly extending the recent work of Nerem et al. [2025] by allowing for a differentiable regularization loss. Empirical results largely support our theoretical findings.
In recent years, there has been growing interest in understanding neural architectures' ability to learn to execute discrete algorithms, a line of work often referred to as neural algorithmic reasoning. The goal is to integrate algorithmic reasoning capabilities into larger neural pipelines. Many such architectures are based on (message-passing) graph neural networks (MPNNs), owing to their permutation equivariance and ability to deal with sparsity and variable-sized inputs. However, existing work is either largely empirical and lacks formal guarantees or it focuses solely on expressivity, leaving open the question of when and how such architectures generalize beyond a finite training set. In this work, we propose a general theoretical framework that characterizes the sufficient conditions under which MPNNs can learn an algorithm from a training set of small instances and provably approximate its behavior on inputs of arbitrary size. Our framework applies to a broad class of algorithms, including single-source shortest paths, minimum spanning trees, and general dynamic programming problems, such as the $0$-$1$ knapsack problem. In addition, we establish impossibility results for a wide range of algorithmic tasks, showing that standard MPNNs cannot learn them, and we derive more expressive MPNN-like architectures that overcome these limitations. Finally, we refine our analysis for the Bellman-Ford algorithm, yielding a substantially smaller required training set and significantly extending the recent work of Nerem et al. [2025] by allowing for a differentiable regularization loss. Empirical results largely support our theoretical findings.
Authors: Antoine Amarilli, Sebastien Labbe, Charles Paperman
We introduce the task of out-of-order membership to a formal language L, where the letters of a word w are revealed one by one in an adversarial order. The length |w| is known in advance, but the content of w is streamed as pairs (i, w[i]), received exactly once for each position i, in arbitrary order. We study efficient algorithms for this task when L is regular, seeking tight complexity bounds as a function of |w| for a fixed target language. Most of our results apply to an algebraically defined variant dubbed out-of-order evaluation: this problem is defined for a fixed finite monoid or semigroup S, and our goal is to compute the ordered product of the streamed elements of w.
We show that, for any fixed regular language or finite semigroup, both problems can be solved in constant time per streamed symbol and in linear space. However, the precise space complexity strongly depends on the algebraic structure of the target language or evaluation semigroup. Our main contributions are therefore to show (deterministic) space complexity characterizations, which we do for out-of-order evaluation of monoids and semigroups.
For monoids, we establish a trichotomy: the space complexity is either Θ(1), Θ(log n), or Θ(n), where n = |w|. More specifically, the problem admits a constant-space solution for commutative monoids, while all non-commutative monoids require Ω(log n) space. We further identify a class of monoids admitting an O(log n)-space algorithm, and show that all remaining monoids require Ω(n) space.
For general semigroups, the situation is more intricate. We characterize a class of semigroups admitting constant-space algorithms for out-of-order evaluation, and show that semigroups outside this class require at least Ω(log n) space.
We introduce the task of out-of-order membership to a formal language L, where the letters of a word w are revealed one by one in an adversarial order. The length |w| is known in advance, but the content of w is streamed as pairs (i, w[i]), received exactly once for each position i, in arbitrary order. We study efficient algorithms for this task when L is regular, seeking tight complexity bounds as a function of |w| for a fixed target language. Most of our results apply to an algebraically defined variant dubbed out-of-order evaluation: this problem is defined for a fixed finite monoid or semigroup S, and our goal is to compute the ordered product of the streamed elements of w.
We show that, for any fixed regular language or finite semigroup, both problems can be solved in constant time per streamed symbol and in linear space. However, the precise space complexity strongly depends on the algebraic structure of the target language or evaluation semigroup. Our main contributions are therefore to show (deterministic) space complexity characterizations, which we do for out-of-order evaluation of monoids and semigroups.
For monoids, we establish a trichotomy: the space complexity is either Θ(1), Θ(log n), or Θ(n), where n = |w|. More specifically, the problem admits a constant-space solution for commutative monoids, while all non-commutative monoids require Ω(log n) space. We further identify a class of monoids admitting an O(log n)-space algorithm, and show that all remaining monoids require Ω(n) space.
For general semigroups, the situation is more intricate. We characterize a class of semigroups admitting constant-space algorithms for out-of-order evaluation, and show that semigroups outside this class require at least Ω(log n) space.
Authors: Tomáš Masařík, Michał Włodarczyk, Mehmet Akif Yıldız
We consider the problem of partitioning the edges of a graph into as few paths as possible. This is a~subject of the classic conjecture of Gallai and a recurring topic in combinatorics. Regarding the complexity of partitioning a graph optimally, Peroché [Discret. Appl. Math., 1984] proved that it is NP-hard already on graphs of maximum degree four, even when we only ask if two paths suffice.
We show that the problem is solvable in polynomial time on subcubic graphs and then we present an efficient algorithm for ``almost-subcubic'' graphs. Precisely, we prove that the problem is fixed-parameter tractable when parameterized by the edge-deletion distance to a subcubic graph. To this end, we reduce the task to model checking in first-order logic extended by disjoint-paths predicates ($\mathsf{FO}\text{+}\mathsf{DP}$) and then we employ the recent tractability result by Schirrmacher, Siebertz, Stamoulis, Thilikos, and Vigny [LICS 2024].
We consider the problem of partitioning the edges of a graph into as few paths as possible. This is a~subject of the classic conjecture of Gallai and a recurring topic in combinatorics. Regarding the complexity of partitioning a graph optimally, Peroché [Discret. Appl. Math., 1984] proved that it is NP-hard already on graphs of maximum degree four, even when we only ask if two paths suffice.
We show that the problem is solvable in polynomial time on subcubic graphs and then we present an efficient algorithm for ``almost-subcubic'' graphs. Precisely, we prove that the problem is fixed-parameter tractable when parameterized by the edge-deletion distance to a subcubic graph. To this end, we reduce the task to model checking in first-order logic extended by disjoint-paths predicates ($\mathsf{FO}\text{+}\mathsf{DP}$) and then we employ the recent tractability result by Schirrmacher, Siebertz, Stamoulis, Thilikos, and Vigny [LICS 2024].
Authors: Timo Gervens, Martin Grohe, Louis Härtel, Philipp Silva da Fonseca
We revisit the algorithmic problem of reconstructing a graph from homomorphism counts that has first been studied in (Böker et al., STACS 2024): given graphs $F_1,\ldots,F_k$ and counts $m_1,\ldots,m_k$, decide if there is a graph $G$ such that the number of homomorphisms from $F_i$ to $G$ is $m_i$, for all $i$. We prove that the problem is NEXP-hard if the counts $m_i$ are specified in binary and $Σ_2^p$-complete if they are in unary.
Furthermore, as a positive result, we show that the unary version can be solved in polynomial time if the constraint graphs are stars of bounded size.
We revisit the algorithmic problem of reconstructing a graph from homomorphism counts that has first been studied in (Böker et al., STACS 2024): given graphs $F_1,\ldots,F_k$ and counts $m_1,\ldots,m_k$, decide if there is a graph $G$ such that the number of homomorphisms from $F_i$ to $G$ is $m_i$, for all $i$. We prove that the problem is NEXP-hard if the counts $m_i$ are specified in binary and $Σ_2^p$-complete if they are in unary.
Furthermore, as a positive result, we show that the unary version can be solved in polynomial time if the constraint graphs are stars of bounded size.
Authors: Alexander Lindermayr, Guido Schäfer, Jens Schlöter, Leen Stougie
We consider the problem of online preemptive scheduling on a single machine to minimize the total flow time. In clairvoyant scheduling, where job processing times are revealed upon arrival, the Shortest Remaining Processing Time (SRPT) algorithm is optimal. In practice, however, exact processing times are often unknown. At the opposite extreme, non-clairvoyant scheduling, in which processing times are revealed only upon completion, suffers from strong lower bounds on the competitive ratio. This motivates the study of intermediate information models. We introduce a new model in which processing times are revealed gradually during execution. Each job consists of a sequence of operations, and the processing time of an operation becomes known only after the preceding one completes. This models many scheduling scenarios that arise in computing systems.
Our main result is a deterministic $O(m^2)$-competitive algorithm, where $m$ is the maximum number of operations per job. More specifically, we prove a refined competitive ratio in $O(m_1 \cdot m_2)$, where $m_1$ and $m_2$ are instance-dependent parameters describing the operation size structure. Our algorithm and analysis build on recent advancements in robust flow time minimization (SODA '26), where jobs arrive with estimated sizes. However, in our setting we have no bounded estimate on a job's processing time. Thus, we design a highly adaptive algorithm that gradually explores a job's operations while working on them, and groups them into virtual chunks whose size can be well-estimated. This is a crucial ingredient of our result and requires a much more careful analysis compared to the robust setting. We also provide lower bounds showing that our bounds are essentially best possible. For the special case of scheduling with uniform obligatory tests, we show that SRPT at the operation level is $2$-competitive, which is best possible.
We consider the problem of online preemptive scheduling on a single machine to minimize the total flow time. In clairvoyant scheduling, where job processing times are revealed upon arrival, the Shortest Remaining Processing Time (SRPT) algorithm is optimal. In practice, however, exact processing times are often unknown. At the opposite extreme, non-clairvoyant scheduling, in which processing times are revealed only upon completion, suffers from strong lower bounds on the competitive ratio. This motivates the study of intermediate information models. We introduce a new model in which processing times are revealed gradually during execution. Each job consists of a sequence of operations, and the processing time of an operation becomes known only after the preceding one completes. This models many scheduling scenarios that arise in computing systems.
Our main result is a deterministic $O(m^2)$-competitive algorithm, where $m$ is the maximum number of operations per job. More specifically, we prove a refined competitive ratio in $O(m_1 \cdot m_2)$, where $m_1$ and $m_2$ are instance-dependent parameters describing the operation size structure. Our algorithm and analysis build on recent advancements in robust flow time minimization (SODA '26), where jobs arrive with estimated sizes. However, in our setting we have no bounded estimate on a job's processing time. Thus, we design a highly adaptive algorithm that gradually explores a job's operations while working on them, and groups them into virtual chunks whose size can be well-estimated. This is a crucial ingredient of our result and requires a much more careful analysis compared to the robust setting. We also provide lower bounds showing that our bounds are essentially best possible. For the special case of scheduling with uniform obligatory tests, we show that SRPT at the operation level is $2$-competitive, which is best possible.
Authors: Ho-Lin Chen, Tsun Ming Cheung, Peng-Ting Lin, Meng-Tsung Tsai
We study the space complexity of computing a sparse subgraph of a directed graph that certifies connectivity in the streaming and distributed models. Formally, for a directed graph $G=(V,A)$ and $k\in \mathbb{N}$, a $k$-node strong connectivity certificate is a subgraph $H=(V,A')\subseteq G$ such that for every pair of distinct nodes $s,t\in V$, the number of pairwise internally node-disjoint paths from $s$ to $t$ in $H$ is at least $k$ or the corresponding number in $G$. In light of the inherent hardness of directed connectivity problems, several prior work focused on restricted graph classes, showing that several problems that are hard in general become efficiently solvable when the input graph is a tournament (i.e., a directed complete graph) (Chakrabarti et al. [SODA 2020]; Baweja, Jia, and Woddruff [ITCS 2022]), or close to a tournament in edit distance (Ghosh and Kuchlous [ESA 2024]). Extending this line of work, our main result shows, at a qualitative level, that the streaming complexity of strong connectivity certificates and related problems is parameterized by independence number, demonstrating a continuum of hardness for directed graph connectivity problems. Quantitatively, for an $n$-node graph with independence number $α$, we give $p$-pass randomized algorithms that compute a $k$-node strong connectivity certificate of size $O(αn)$ using $\tilde{O}(k^{1-1/p}αn^{1+1/p})$ space in the insertion-only model. For the lower bound, we show that even when $k=1$, any $p$-pass streaming algorithm for a 1-node strong connectivity certificate in the insertion-only model requires $Ω(αn/p)$ space. To derive these lower bounds, we introduce the gadget-embedding tournament framework to construct direct-sum-type hard instances with a prescribed independence number, which is applicable to lower-bounding a wide range of directed graph problems.
We study the space complexity of computing a sparse subgraph of a directed graph that certifies connectivity in the streaming and distributed models. Formally, for a directed graph $G=(V,A)$ and $k\in \mathbb{N}$, a $k$-node strong connectivity certificate is a subgraph $H=(V,A')\subseteq G$ such that for every pair of distinct nodes $s,t\in V$, the number of pairwise internally node-disjoint paths from $s$ to $t$ in $H$ is at least $k$ or the corresponding number in $G$. In light of the inherent hardness of directed connectivity problems, several prior work focused on restricted graph classes, showing that several problems that are hard in general become efficiently solvable when the input graph is a tournament (i.e., a directed complete graph) (Chakrabarti et al. [SODA 2020]; Baweja, Jia, and Woddruff [ITCS 2022]), or close to a tournament in edit distance (Ghosh and Kuchlous [ESA 2024]). Extending this line of work, our main result shows, at a qualitative level, that the streaming complexity of strong connectivity certificates and related problems is parameterized by independence number, demonstrating a continuum of hardness for directed graph connectivity problems. Quantitatively, for an $n$-node graph with independence number $α$, we give $p$-pass randomized algorithms that compute a $k$-node strong connectivity certificate of size $O(αn)$ using $\tilde{O}(k^{1-1/p}αn^{1+1/p})$ space in the insertion-only model. For the lower bound, we show that even when $k=1$, any $p$-pass streaming algorithm for a 1-node strong connectivity certificate in the insertion-only model requires $Ω(αn/p)$ space. To derive these lower bounds, we introduce the gadget-embedding tournament framework to construct direct-sum-type hard instances with a prescribed independence number, which is applicable to lower-bounding a wide range of directed graph problems.
Authors: Yen-Cheng Chang, Tsun Ming Cheung, Meng-Tsung Tsai, Ting-An Wu
The geometric congruence problem is a fundamental building block in many computer vision and image recognition tasks. This problem considers the decision task of whether two point sets are congruent under translation and rotation. A related and more general problem, geometric hashing, considers the task of compactly encoding multiple point sets for efficient congruence queries. Despite its wide applications, both problems have received little prior attention in space-aware settings.
In this work, we study the two-dimensional congruence testing and geometric hashing problem in the streaming model, where data arrive as a stream and the primary goal is to minimize the space usage. To meaningfully analyze space complexity, we address the underaddressed issue of input precision by working in the finite-precision rational setting: the input point coordinates are rational numbers of the form $p/q$ with $|p|, |q| \le U$.
Our result considers a stronger variant of congruence testing called congruence identification, for which we obtain a 3-pass randomized streaming algorithm using $O(\log n(\log U+\log n))$ space. Using the congruence identification algorithm as a building block, we give a 6-pass $O(m\log n (\log n + \log U + \log m))$-space randomized streaming algorithm that outputs a hash function of length $O(\log n+\log U+\log m)$.
Our key technical tool for achieving space efficiency is the use of complex moments. While complex moment methods are widely employed as heuristics in object recognition, their effectiveness is often limited by vanishing moment issues (Flusser and Suk [IEEE Trans. Image Process 2006]). We show that, in the rational setting, it suffices to track only $O(\log n)$ complex moments to ensure a non-vanishing moment, thus providing a sound theoretical guarantee for recovering a valid rotation in positive instances.
The geometric congruence problem is a fundamental building block in many computer vision and image recognition tasks. This problem considers the decision task of whether two point sets are congruent under translation and rotation. A related and more general problem, geometric hashing, considers the task of compactly encoding multiple point sets for efficient congruence queries. Despite its wide applications, both problems have received little prior attention in space-aware settings.
In this work, we study the two-dimensional congruence testing and geometric hashing problem in the streaming model, where data arrive as a stream and the primary goal is to minimize the space usage. To meaningfully analyze space complexity, we address the underaddressed issue of input precision by working in the finite-precision rational setting: the input point coordinates are rational numbers of the form $p/q$ with $|p|, |q| \le U$.
Our result considers a stronger variant of congruence testing called congruence identification, for which we obtain a 3-pass randomized streaming algorithm using $O(\log n(\log U+\log n))$ space. Using the congruence identification algorithm as a building block, we give a 6-pass $O(m\log n (\log n + \log U + \log m))$-space randomized streaming algorithm that outputs a hash function of length $O(\log n+\log U+\log m)$.
Our key technical tool for achieving space efficiency is the use of complex moments. While complex moment methods are widely employed as heuristics in object recognition, their effectiveness is often limited by vanishing moment issues (Flusser and Suk [IEEE Trans. Image Process 2006]). We show that, in the rational setting, it suffices to track only $O(\log n)$ complex moments to ensure a non-vanishing moment, thus providing a sound theoretical guarantee for recovering a valid rotation in positive instances.
