Theory of Computing Report

Authors: Xin Li, Hanlin Ren, Yan Zhong

For a propositional proof system $\mathcal{P}$ and a polynomial-time function $G: \{0, 1\}^n \to \{0, 1\}^N$ ($N > 10n$), we say that $G$ is a *proof complexity generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the (suitably encoded) statement "$y\not\in\mathrm{Range}(G)$" for every $y \in \{0, 1\}^N$, and $G$ is a *demi-bits generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the statement "$y \not\in\mathrm{Range}(G)$" for a noticeable fraction of $y \in \{0, 1\}^N$. As can be seen from the definitions, proof complexity generators are qualitatively stronger objects than demi-bits generators. Our main result is that, perhaps counter-intuitively, every demi-bits generator "contains" exponentially many proof complexity generators. In fact, a random subset of output bits of a demi-bits generator forms a proof complexity generator with constant probability. This result is an extremely simple corollary of Pajor's Lemma (a strengthening of the well-known Sauer--Shelah Lemma). This result allows us to exhibit the hardness of the Range Avoidance problem ($\text{Avoid}$) in several new, restricted settings of interest. Along the way, we introduce the notion of *zero-error disperser families* that can transform demi-bits generators into proof complexity generators, and show that this family can be computed by projections (i.e., without any circuit complexity overhead). Using a different instantiation of this family, we construct proof complexity generators from *barely non-trivial* demi-bits generators $G: \{0, 1\}^n \to \{0, 1\}^N$, where the number of hard-to-prove statements of the form "$y \not \in \mathrm{Range}(G)$" just slightly exceeds $2^n$ (which is the number of *false* statements of this form).

Authors: Xin Li, Hanlin Ren, Yan Zhong

For a propositional proof system $\mathcal{P}$ and a polynomial-time function $G: \{0, 1\}^n \to \{0, 1\}^N$ ($N > 10n$), we say that $G$ is a *proof complexity generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the (suitably encoded) statement "$y\not\in\mathrm{Range}(G)$" for every $y \in \{0, 1\}^N$, and $G$ is a *demi-bits generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the statement "$y \not\in\mathrm{Range}(G)$" for a noticeable fraction of $y \in \{0, 1\}^N$. As can be seen from the definitions, proof complexity generators are qualitatively stronger objects than demi-bits generators. Our main result is that, perhaps counter-intuitively, every demi-bits generator "contains" exponentially many proof complexity generators. In fact, a random subset of output bits of a demi-bits generator forms a proof complexity generator with constant probability. This result is an extremely simple corollary of Pajor's Lemma (a strengthening of the well-known Sauer--Shelah Lemma). This result allows us to exhibit the hardness of the Range Avoidance problem ($\text{Avoid}$) in several new, restricted settings of interest. Along the way, we introduce the notion of *zero-error disperser families* that can transform demi-bits generators into proof complexity generators, and show that this family can be computed by projections (i.e., without any circuit complexity overhead). Using a different instantiation of this family, we construct proof complexity generators from *barely non-trivial* demi-bits generators $G: \{0, 1\}^n \to \{0, 1\}^N$, where the number of hard-to-prove statements of the form "$y \not \in \mathrm{Range}(G)$" just slightly exceeds $2^n$ (which is the number of *false* statements of this form).

Tuesday, September 22 2026, 00:00

An exponential lower bound for the bit pigeonhole principle in resolution over parities

Authors: Kamil Braun

Resolution over parities, $\mathrm{Res}(\oplus)$, is the characteristic-two version of resolution over linear equations: clauses are disjunctions of affine equations over $\mathbb F_2$. Superpolynomial size lower bounds were previously known only for restricted refutations: tree-like, regular, or of bounded depth. We prove that every DAG-like $\mathrm{Res} (\oplus)$ refutation of the bit pigeonhole principle with $n+1$ pigeons and $n=2^\ell$ holes has more than $\exp(n/(32768\ell^2))=2^{Ω(n/\log^2 n)}$ clauses, for every $\ell\ge32$, with no restriction on regularity or depth. The proof translates an arbitrary refutation with $S$ clauses into a polynomial calculus refutation of degree $O(\log n)$ over $O(S+n^2)$ groups of extension variables in the style of Buss, Impagliazzo, Krajicek, Pudlak, Razborov, and Sgall. One substitution then removes all extension variables at once and leaves a nonzero low-degree polynomial derived from the pigeonhole axioms alone at degree at most $n/2$; a degree lower bound in the style of Razborov, proved through the homology of chessboard complexes, shows that no such derivation exists. The argument also yields a general sufficient condition for $\mathrm{Res}(\oplus)$ size lower bounds. The main theorem, this condition, and all their dependencies are formalized in Lean 4, and every statement links to its formal proof. The proof was developed with substantial AI assistance within an open research framework described in the final section.

Authors: Kamil Braun

Resolution over parities, $\mathrm{Res}(\oplus)$, is the characteristic-two version of resolution over linear equations: clauses are disjunctions of affine equations over $\mathbb F_2$. Superpolynomial size lower bounds were previously known only for restricted refutations: tree-like, regular, or of bounded depth. We prove that every DAG-like $\mathrm{Res} (\oplus)$ refutation of the bit pigeonhole principle with $n+1$ pigeons and $n=2^\ell$ holes has more than $\exp(n/(32768\ell^2))=2^{Ω(n/\log^2 n)}$ clauses, for every $\ell\ge32$, with no restriction on regularity or depth. The proof translates an arbitrary refutation with $S$ clauses into a polynomial calculus refutation of degree $O(\log n)$ over $O(S+n^2)$ groups of extension variables in the style of Buss, Impagliazzo, Krajicek, Pudlak, Razborov, and Sgall. One substitution then removes all extension variables at once and leaves a nonzero low-degree polynomial derived from the pigeonhole axioms alone at degree at most $n/2$; a degree lower bound in the style of Razborov, proved through the homology of chessboard complexes, shows that no such derivation exists. The argument also yields a general sufficient condition for $\mathrm{Res}(\oplus)$ size lower bounds. The main theorem, this condition, and all their dependencies are formalized in Lean 4, and every statement links to its formal proof. The proof was developed with substantial AI assistance within an open research framework described in the final section.

Tuesday, September 22 2026, 00:00

Sumset Structure in Local Computation

Authors: Alexander Golovnev, Mohit Gurumukhani

We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study $\ell$-local decision trees, in which each internal node queries an $\ell$-local function of the input. We show that sufficiently strong lower bounds for $\ell$-local decision trees would imply several breakthrough circuit lower bounds, including super-linear size lower bounds for log-depth circuits and improved bounds for unrestricted-depth circuits. Previously, such consequences were known to follow from strong lower bounds for depth-$3$ circuits, which has been the main prior approach in attempting to prove these results. Since local decision trees are strictly weaker than depth-$3$ circuits, this provides a formally easier route to the same circuit lower-bound consequences. We prove essentially optimal lower bounds for a weaker variant that we call oblivious $\ell$-local decision trees, where all nodes at the same depth query the same function. Our lower bounds follow from a new technique that uncovers sumset structure in local maps, and our hard functions are sumset dispersers, sumset condensers, and directional affine dispersers. Along the way, we give an explicit construction of a sumset condenser with small entropy loss. As an additional contribution, we initiate the study of degree-$2$ decision trees, in which each query is a quadratic polynomial of the input. We show that proving lower bounds in this model is a natural stepping stone toward constructing dispersers for degree-$2$ variety sources, which imply improved circuit lower bounds for unrestricted depth circuits. We prove nearly maximal lower bounds for the oblivious variant of the model.

Authors: Alexander Golovnev, Mohit Gurumukhani

We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study $\ell$-local decision trees, in which each internal node queries an $\ell$-local function of the input. We show that sufficiently strong lower bounds for $\ell$-local decision trees would imply several breakthrough circuit lower bounds, including super-linear size lower bounds for log-depth circuits and improved bounds for unrestricted-depth circuits. Previously, such consequences were known to follow from strong lower bounds for depth-$3$ circuits, which has been the main prior approach in attempting to prove these results. Since local decision trees are strictly weaker than depth-$3$ circuits, this provides a formally easier route to the same circuit lower-bound consequences. We prove essentially optimal lower bounds for a weaker variant that we call oblivious $\ell$-local decision trees, where all nodes at the same depth query the same function. Our lower bounds follow from a new technique that uncovers sumset structure in local maps, and our hard functions are sumset dispersers, sumset condensers, and directional affine dispersers. Along the way, we give an explicit construction of a sumset condenser with small entropy loss. As an additional contribution, we initiate the study of degree-$2$ decision trees, in which each query is a quadratic polynomial of the input. We show that proving lower bounds in this model is a natural stepping stone toward constructing dispersers for degree-$2$ variety sources, which imply improved circuit lower bounds for unrestricted depth circuits. We prove nearly maximal lower bounds for the oblivious variant of the model.

Tuesday, September 22 2026, 00:00

Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance

Authors: Rafail Ostrovsky

We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c >0$, where $N$ is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to $Ω(N)$ and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical $X$- and $Z$-check spaces, and with a constant rate and constant relative distance. For every fixed $λ>1$, there is a constant $c>0$ such that hardness still holds even when every nonidentity stabilizer has weight greater than $λ$ times the quantum distance. We also improve the hardness gap of graph state distance on $N$ vertices of Grigorescu, Jha, and Samperton from cube-root to $Ω(N)$, resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most $N$. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code $C$ of length $m$ into a self-dual code $A(C)$ of length $N=Θ(m)$ while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of $C$. It comes with a linear embedding $τ: \mathbb F_2^m \hookrightarrow \mathbb F_2^N$. The embedding doubles all Hamming distances between vectors in $\mathbb F_2^m$ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of $A(C)$ of weight at most $2m$ are exactly $τ(C)$.

Authors: Rafail Ostrovsky

We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c >0$, where $N$ is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to $Ω(N)$ and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical $X$- and $Z$-check spaces, and with a constant rate and constant relative distance. For every fixed $λ>1$, there is a constant $c>0$ such that hardness still holds even when every nonidentity stabilizer has weight greater than $λ$ times the quantum distance. We also improve the hardness gap of graph state distance on $N$ vertices of Grigorescu, Jha, and Samperton from cube-root to $Ω(N)$, resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most $N$. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code $C$ of length $m$ into a self-dual code $A(C)$ of length $N=Θ(m)$ while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of $C$. It comes with a linear embedding $τ: \mathbb F_2^m \hookrightarrow \mathbb F_2^N$. The embedding doubles all Hamming distances between vectors in $\mathbb F_2^m$ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of $A(C)$ of weight at most $2m$ are exactly $τ(C)$.

Tuesday, September 22 2026, 00:00

Interval number for tournaments in P3-convexity

Authors: Idian C. Capozzoli, Yan S. Couto, Enrique Junchaya

We study the complexity of determining the interval numbers of tournaments in the $\overrightarrow{P_3}$ and $\overrightarrow{P_3^*}$ convexities, denoted by $\overrightarrow{\mathrm{in}}_{P_3}(T)$ and $\overrightarrow{\mathrm{in}}_{P_3^*}(T)$ on a tournament $T$. For each $\overrightarrow{\mathcal{X}} \in \{\overrightarrow{P_3}, \overrightarrow{P_3^*}\}$, we show that determining whether $\overrightarrow{\mathrm{in}}_{\mathcal{X}}(T) \leq k$ is W[2]-complete when parameterized by $k$. Moreover, under ETH, we show that there is no parameterized algorithm for that problem with running time $f(k)\, n^{o(k)}$ on an $n$-vertex tournament, where $f$ is any computable function. For the $\overrightarrow{P_3}$-convexity, we also show that $\overrightarrow{\mathrm{in}}_{P_3}(T) = \mathcal{O}(\log n)$, which yields a simple quasi-polynomial $n^{\mathcal{O}(\log n)}$ brute-force algorithm. On the other hand, under ETH, we show that the problem is NP-intermediate, that is, it is neither NP-hard nor in P. For the $\overrightarrow{P_3^*}$-convexity, the same brute force algorithm is not quasi-polynomial, since we present a family of instances with $\overrightarrow{\mathrm{in}}_{P_3^*}(T) = Θ(n)$. We conjecture that this problem is NP-complete.

Authors: Idian C. Capozzoli, Yan S. Couto, Enrique Junchaya

We study the complexity of determining the interval numbers of tournaments in the $\overrightarrow{P_3}$ and $\overrightarrow{P_3^*}$ convexities, denoted by $\overrightarrow{\mathrm{in}}_{P_3}(T)$ and $\overrightarrow{\mathrm{in}}_{P_3^*}(T)$ on a tournament $T$. For each $\overrightarrow{\mathcal{X}} \in \{\overrightarrow{P_3}, \overrightarrow{P_3^*}\}$, we show that determining whether $\overrightarrow{\mathrm{in}}_{\mathcal{X}}(T) \leq k$ is W[2]-complete when parameterized by $k$. Moreover, under ETH, we show that there is no parameterized algorithm for that problem with running time $f(k)\, n^{o(k)}$ on an $n$-vertex tournament, where $f$ is any computable function. For the $\overrightarrow{P_3}$-convexity, we also show that $\overrightarrow{\mathrm{in}}_{P_3}(T) = \mathcal{O}(\log n)$, which yields a simple quasi-polynomial $n^{\mathcal{O}(\log n)}$ brute-force algorithm. On the other hand, under ETH, we show that the problem is NP-intermediate, that is, it is neither NP-hard nor in P. For the $\overrightarrow{P_3^*}$-convexity, the same brute force algorithm is not quasi-polynomial, since we present a family of instances with $\overrightarrow{\mathrm{in}}_{P_3^*}(T) = Θ(n)$. We conjecture that this problem is NP-complete.

Tuesday, September 22 2026, 00:00

Strong NP-Completeness of Unrestricted Balanced Mobiles

Authors: Andrei Popa, Alexandru Popa

A mobile is a rooted full binary tree whose leaves carry positive integer weights. The imbalance of an internal node is the absolute difference between the total weights of its two child subtrees, and the cost of the mobile is the sum of these imbalances. In the unrestricted \emph{Balanced Mobiles} problem, only the multiset of leaf weights is given: both the tree topology and the placement of the weights must be chosen so as to minimize the cost. The computational complexity of this unrestricted variant has remained open, although the variant with a prescribed topology is strongly NP-hard. We close this gap by proving that the decision version of unrestricted Balanced Mobiles is strongly NP-complete. Our reduction from Numerical 3-Dimensional Matching with Distinct Integers uses three widely separated numerical scales. Tight telescoping bounds force every threshold-achieving mobile into a canonical hierarchy, after which pairwise distinctness of the source integers collapses the hierarchy to single triples from which a valid numerical matching can be recovered.

Authors: Andrei Popa, Alexandru Popa

A mobile is a rooted full binary tree whose leaves carry positive integer weights. The imbalance of an internal node is the absolute difference between the total weights of its two child subtrees, and the cost of the mobile is the sum of these imbalances. In the unrestricted \emph{Balanced Mobiles} problem, only the multiset of leaf weights is given: both the tree topology and the placement of the weights must be chosen so as to minimize the cost. The computational complexity of this unrestricted variant has remained open, although the variant with a prescribed topology is strongly NP-hard. We close this gap by proving that the decision version of unrestricted Balanced Mobiles is strongly NP-complete. Our reduction from Numerical 3-Dimensional Matching with Distinct Integers uses three widely separated numerical scales. Tight telescoping bounds force every threshold-achieving mobile into a canonical hierarchy, after which pairwise distinctness of the source integers collapses the hierarchy to single triples from which a valid numerical matching can be recovered.

Tuesday, September 22 2026, 00:00

Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces

Authors: Hans Raj Tiwary, Michel Grabisch

We study the computational complexity of fundamental algorithmic problems -- membership testing, separation, valid-inequality testing, and linear optimization -- over polytopes and cones arising from cooperative games (also known as pseudo-Boolean functions). A central obstacle in the study of such problems is that a general cooperative game on $n$ players requires $2^n$ values, so the input size is $2^n$ for a game with $n$ players, making these computational tasks theoretically trivial. Restricting to $k$-additive games reduces the input size to $O(n^k)$, making such games a natural target for meaningful questions about the existence of efficient algorithms. On the positive side, we give an explicit extended formulation of size $O(n^k)$ for the core of $k$-additive $k$-monotone games, allowing all four problems to be solved by a single polynomial-size linear program -- in particular, circumventing the ellipsoid method that is needed when building from earlier tractability results of Deng and Papadimitriou, or of Edmonds. For the cone of $k$-additive $(k{-}1)$-monotone games, we give a complete characterization of its extreme rays and derive the same $O(n^k)$ bound on extension complexity, yielding a geometry-based proof and generalization of a result of Billionnet and Minoux. On the negative side, we show that for $l \leq k-2$ the cone of $k$-additive $l$-monotone games is computationally intractable: membership testing is not in NP (unless NP\,=\,coNP), valid-inequality testing is NP-complete, and extension complexity is at least $1.5^n$. Our hardness results yield, as a special case, a result of Crama and of Gallo and Simone. Furthermore, our hardness results also explain the lack of any good characterization of the extreme rays of the cone of $k$-additive $(k{-}2)$-monotone games.

Authors: Hans Raj Tiwary, Michel Grabisch

We study the computational complexity of fundamental algorithmic problems -- membership testing, separation, valid-inequality testing, and linear optimization -- over polytopes and cones arising from cooperative games (also known as pseudo-Boolean functions). A central obstacle in the study of such problems is that a general cooperative game on $n$ players requires $2^n$ values, so the input size is $2^n$ for a game with $n$ players, making these computational tasks theoretically trivial. Restricting to $k$-additive games reduces the input size to $O(n^k)$, making such games a natural target for meaningful questions about the existence of efficient algorithms. On the positive side, we give an explicit extended formulation of size $O(n^k)$ for the core of $k$-additive $k$-monotone games, allowing all four problems to be solved by a single polynomial-size linear program -- in particular, circumventing the ellipsoid method that is needed when building from earlier tractability results of Deng and Papadimitriou, or of Edmonds. For the cone of $k$-additive $(k{-}1)$-monotone games, we give a complete characterization of its extreme rays and derive the same $O(n^k)$ bound on extension complexity, yielding a geometry-based proof and generalization of a result of Billionnet and Minoux. On the negative side, we show that for $l \leq k-2$ the cone of $k$-additive $l$-monotone games is computationally intractable: membership testing is not in NP (unless NP\,=\,coNP), valid-inequality testing is NP-complete, and extension complexity is at least $1.5^n$. Our hardness results yield, as a special case, a result of Crama and of Gallo and Simone. Furthermore, our hardness results also explain the lack of any good characterization of the extreme rays of the cone of $k$-additive $(k{-}2)$-monotone games.

Tuesday, September 22 2026, 00:00

Constant-Coin Complete-Information Debates for $\mathsf{P}$ with Arbitrarily Small Strong Error

Authors: M. Utkan Gezer

We study complete-information debate systems in which a probabilistic finite-state verifier reads the alternating messages of a prover and a refuter. Demirci, Say, and Yakaryılmaz showed that every language in $\mathsf{P}$ has such debates checkable with a constant number of random bits and arbitrarily small weak error. Their strong-error construction, which also counts nontermination as failure, did not permit arbitrary error reduction. We close this gap: for every $L\in\mathsf{P}$ and every $\varepsilon>0$, there is a constant-space verifier using a constant number of private coin tosses that has perfect completeness and strong error at most $\varepsilon$. The verifier simulates a polynomial-time alternating multihead finite automaton, privately spot-checking one of its input heads. The key observation is that, on a nonmember, the refuter may concede any round in which the prover first misreports a head reading. This ensures termination against every prover when the refuter follows the specified strategy, and permits strong-error reduction by repetition.

Authors: M. Utkan Gezer

We study complete-information debate systems in which a probabilistic finite-state verifier reads the alternating messages of a prover and a refuter. Demirci, Say, and Yakaryılmaz showed that every language in $\mathsf{P}$ has such debates checkable with a constant number of random bits and arbitrarily small weak error. Their strong-error construction, which also counts nontermination as failure, did not permit arbitrary error reduction. We close this gap: for every $L\in\mathsf{P}$ and every $\varepsilon>0$, there is a constant-space verifier using a constant number of private coin tosses that has perfect completeness and strong error at most $\varepsilon$. The verifier simulates a polynomial-time alternating multihead finite automaton, privately spot-checking one of its input heads. The key observation is that, on a nonmember, the refuter may concede any round in which the prover first misreports a head reading. This ensures termination against every prover when the refuter follows the specified strategy, and permits strong-error reduction by repetition.

Tuesday, September 22 2026, 00:00

Formalizing PARITY Circuit Lower Bounds in Lean

Authors: Saint Wesonga

We formalize Hastad's PARITY lower bound in Lean using the switching lemma. For every fixed d >= 2, formulas and DAG circuits of computation depth at most d computing PARITY on n inputs require size exp(Omega_d(n^(1/(d-1)))) for all sufficiently large n. This matches the classical upper bound up to constants in the exponent and implies that PARITY is not in nonuniform AC0. We also construct a polynomial-size, logarithmic-depth bounded-fan-in formula family for PARITY, providing a witness to NC1 is not a subset of AC0 for the formalized models. The Lean source code is available at github.com/formalcs/circuit-complexity and is checked with Lean 4.33.1 and mathlib 4.33.1.

Authors: Saint Wesonga

We formalize Hastad's PARITY lower bound in Lean using the switching lemma. For every fixed d >= 2, formulas and DAG circuits of computation depth at most d computing PARITY on n inputs require size exp(Omega_d(n^(1/(d-1)))) for all sufficiently large n. This matches the classical upper bound up to constants in the exponent and implies that PARITY is not in nonuniform AC0. We also construct a polynomial-size, logarithmic-depth bounded-fan-in formula family for PARITY, providing a witness to NC1 is not a subset of AC0 for the formalized models. The Lean source code is available at https://github.com/formalcs/circuit-complexity and is checked with Lean 4.33.1 and mathlib 4.33.1.

Tuesday, September 22 2026, 00:00

Lee-Yang theorem for fermions

Authors: Chaithanya Rayudu, Takahiro Misawa, Andrew Zhao, Jun Takahashi

Lee-Yang theorems are a powerful tool for studying many-body systems, with applications ranging from analyzing phase transitions to proving the efficiency of certain classical and quantum algorithms. In this work, we prove a Lee-Yang zero-freeness theorem for the partition function of a broad class of interacting fermion models, implying the existence of a provably efficient quantum algorithm for estimating their ground-state energies. This class includes several well-known models such as the attractive Hubbard model, repulsive Hubbard model on bipartite graphs, and the interacting Hofstadter model. Our results also rigorously establish the nonexistence of phase transitions in these models in the presence of a nonzero local external field.

Authors: Chaithanya Rayudu, Takahiro Misawa, Andrew Zhao, Jun Takahashi

Lee-Yang theorems are a powerful tool for studying many-body systems, with applications ranging from analyzing phase transitions to proving the efficiency of certain classical and quantum algorithms. In this work, we prove a Lee-Yang zero-freeness theorem for the partition function of a broad class of interacting fermion models, implying the existence of a provably efficient quantum algorithm for estimating their ground-state energies. This class includes several well-known models such as the attractive Hubbard model, repulsive Hubbard model on bipartite graphs, and the interacting Hofstadter model. Our results also rigorously establish the nonexistence of phase transitions in these models in the presence of a nonzero local external field.

Tuesday, September 22 2026, 00:00

Finding a Positive Index Nash Equilibrium is PPADS-Complete

Authors: Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos, Jingming Yan

Every nondegenerate bimatrix game has a Nash equilibrium of Shapley index +1, since all equilibria are isolated, have index +1 or -1, and their indices sum to +1. We prove that the following promise search problem is PPADS-complete: given a rational bimatrix game promised to be nondegenerate, find an exact Nash equilibrium of index +1. To our knowledge, this is the first PPADS-complete equilibrium search problem whose instances are explicit rational normal form payoff matrices, rather than succinct circuits or Turing machines, and thereby addresses an open question posed by Daskalakis [Daskalakis, 2019].

Authors: Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos, Jingming Yan

Every nondegenerate bimatrix game has a Nash equilibrium of Shapley index +1, since all equilibria are isolated, have index +1 or -1, and their indices sum to +1. We prove that the following promise search problem is PPADS-complete: given a rational bimatrix game promised to be nondegenerate, find an exact Nash equilibrium of index +1. To our knowledge, this is the first PPADS-complete equilibrium search problem whose instances are explicit rational normal form payoff matrices, rather than succinct circuits or Turing machines, and thereby addresses an open question posed by Daskalakis [Daskalakis, 2019].

Tuesday, September 22 2026, 00:00

Arc Kayles is PSPACE-complete

Authors: Édouard Bonnet

We show that Arc Kayles is PSPACE-complete. This solves a question raised by Schaefer in 1978.

Authors: Édouard Bonnet

We show that Arc Kayles is PSPACE-complete. This solves a question raised by Schaefer in 1978.

Tuesday, September 22 2026, 00:00

SC Derandomization for Regular ROBPs and Models Beyond BPL

Authors: Kuan Cheng, Ruiyang Wu

We study SC derandomizations for regular read-once branching programs (ROBPs) and computation models beyond BPL. For regular ROBPs with length $n$, width $w$, and multiple accept nodes, we attain three results. 1. When $n \le w$, we show an SC derandomization with space $O(\log^2 n+\log w)$ and error $1/\text{poly}(nw)$. 2. When $n \ge w$, we show an SC derandomization with space $O(\log n \log w)$ and error $1/\text{poly}(w)$. 3. When $w=O(\log n)$, we show an optimal $O(\log n)$ space derandomization with error $1/\text{poly}(w)$. We further show that two super sets of BPL can be computed in SC. 1. For probabilistic logspace TMs with a two-way access random tape, we show that it can be approximated in SC if each entry of the random tape is accessed for at most a constant number of times. 2. For probabilistic logspace TMs with a polynomial size stack, i.e. probabilistic logspace Auxiliary Push-down Machines (AuxPDMs), we show that it can be approximated in SC if the timings of push/pop/idle stack operations do not depend on the randomness. The first model is the read-multiplicity model considered by Impagliazzo, Nisan, Wigderson (STOC'94), in which they show that their INW generator can fool such computations. For the second model, we indicate that it contains candidate languages separating BQL from BPL considered by Apers and Edenhofer (CCC'25).

Authors: Kuan Cheng, Ruiyang Wu

We study SC derandomizations for regular read-once branching programs (ROBPs) and computation models beyond BPL. For regular ROBPs with length $n$, width $w$, and multiple accept nodes, we attain three results. 1. When $n \le w$, we show an SC derandomization with space $O(\log^2 n+\log w)$ and error $1/\text{poly}(nw)$. 2. When $n \ge w$, we show an SC derandomization with space $O(\log n \log w)$ and error $1/\text{poly}(w)$. 3. When $w=O(\log n)$, we show an optimal $O(\log n)$ space derandomization with error $1/\text{poly}(w)$. We further show that two super sets of BPL can be computed in SC. 1. For probabilistic logspace TMs with a two-way access random tape, we show that it can be approximated in SC if each entry of the random tape is accessed for at most a constant number of times. 2. For probabilistic logspace TMs with a polynomial size stack, i.e. probabilistic logspace Auxiliary Push-down Machines (AuxPDMs), we show that it can be approximated in SC if the timings of push/pop/idle stack operations do not depend on the randomness. The first model is the read-multiplicity model considered by Impagliazzo, Nisan, Wigderson (STOC'94), in which they show that their INW generator can fool such computations. For the second model, we indicate that it contains candidate languages separating BQL from BPL considered by Apers and Edenhofer (CCC'25).

Tuesday, September 22 2026, 00:00

The logarithmic spiral is optimal for shoreline search: a computer-assisted proof

Authors: Alexander Temerev

A ship starts at a point of the plane and moves at unit speed; it has to reach an unknown straight line, of which neither the distance nor the direction is known. The competitive ratio of a path is the supremum, over all lines, of the time at which the line is reached divided by its distance. Baeza-Yates, Culberson and Rawlins conjectured that a logarithmic spiral, with ratio $C_{\mathrm{sp}} = 13.8111351794611\ldots$, is optimal. We give a computer-assisted proof. Paths are arbitrary: the distance from the start and the polar angle may both decrease. The proof lifts the set of found directions to the universal cover of the circle, where unfolding the polar angle can only increase it (Kneser-Poulsen on the line); a bookkeeping inequality with a monotone final source then bounds the covered measure by the reward of a three-state relaxed control problem, in which inward motion is an ordinary control and excursions below the guaranteed disk are impulses. An explicit $C^1$ storage function, a tensor cubic B-spline plus a closed-form term, satisfies the dissipation inequalities of that problem at the spiral's level and is tight only at the spiral; this is verified with about $10^6$ boxes of Arb ball arithmetic, an exact jet and an interval Hessian at the spiral.

Authors: Alexander Temerev

A ship starts at a point of the plane and moves at unit speed; it has to reach an unknown straight line, of which neither the distance nor the direction is known. The competitive ratio of a path is the supremum, over all lines, of the time at which the line is reached divided by its distance. Baeza-Yates, Culberson and Rawlins conjectured that a logarithmic spiral, with ratio $C_{\mathrm{sp}} = 13.8111351794611\ldots$, is optimal. We give a computer-assisted proof. Paths are arbitrary: the distance from the start and the polar angle may both decrease. The proof lifts the set of found directions to the universal cover of the circle, where unfolding the polar angle can only increase it (Kneser-Poulsen on the line); a bookkeeping inequality with a monotone final source then bounds the covered measure by the reward of a three-state relaxed control problem, in which inward motion is an ordinary control and excursions below the guaranteed disk are impulses. An explicit $C^1$ storage function, a tensor cubic B-spline plus a closed-form term, satisfies the dissipation inequalities of that problem at the spiral's level and is tight only at the spiral; this is verified with about $10^6$ boxes of Arb ball arithmetic, an exact jet and an interval Hessian at the spiral.

Tuesday, September 22 2026, 00:00

Positive Pair Geometry Matters: Optimal Transport for Contrastive Learning of Visual Representations

Authors: Akshit Nanda, Shahzad Ahmad, Ram Prasad Padhy

Contrastive self-supervised learning has achieved strong performance by learning representations from multiple augmented views of the same image. However, most existing methods construct positive pairs using independently sampled stochastic augmentations, which may alter semantic content and ignore the intrinsic geometry of the data distribution. In this work, we propose OTCLR, an optimal transport-aware framework for contrastive learning representations that generates geometry-consistent positive samples. Instead of directly contrasting two randomly augmented views, we construct intermediate views between the original image and its augmented variants through entropic optimal-transport displacement interpolation. These transport-interpolated samples serve as positive views that better preserve image structure while explicitly modeling spatial distributional geometry. To further promote smooth representation learning, we evaluate auxiliary Sinkhorn regularization terms that encourage transport-interpolated views to remain consistent with their endpoint images. The proposed method can be incorporated into standard contrastive learning pipelines without modifying the encoder architecture. Experiments on multiple benchmark datasets show that our approach improves representation quality and transfer learning performance compared with conventional augmentation-based contrastive learning baselines.

Authors: Akshit Nanda, Shahzad Ahmad, Ram Prasad Padhy

Contrastive self-supervised learning has achieved strong performance by learning representations from multiple augmented views of the same image. However, most existing methods construct positive pairs using independently sampled stochastic augmentations, which may alter semantic content and ignore the intrinsic geometry of the data distribution. In this work, we propose OTCLR, an optimal transport-aware framework for contrastive learning representations that generates geometry-consistent positive samples. Instead of directly contrasting two randomly augmented views, we construct intermediate views between the original image and its augmented variants through entropic optimal-transport displacement interpolation. These transport-interpolated samples serve as positive views that better preserve image structure while explicitly modeling spatial distributional geometry. To further promote smooth representation learning, we evaluate auxiliary Sinkhorn regularization terms that encourage transport-interpolated views to remain consistent with their endpoint images. The proposed method can be incorporated into standard contrastive learning pipelines without modifying the encoder architecture. Experiments on multiple benchmark datasets show that our approach improves representation quality and transfer learning performance compared with conventional augmentation-based contrastive learning baselines.

Tuesday, September 22 2026, 00:00

MR-SPITE: Accelerating Multi-Robot Conflict Scans via Hierarchical Swept-Volume Approximations

Authors: Marta Markowicz, James Motes, Marco Morales, Nancy Amato

Conflict scanning over synchronized robot paths requires detailed collision checking, potentially across every robot pair at every timestep, and may be repeated many times as conflicts are repaired. We present Multi-Robot SPITE (MR-SPITE), a conservative, motion-segment-based filter for accelerating these scans. MR-SPITE partitions each path into temporal intervals and assigns conservative bounds to each segment. An interval scheduler compares bounds for temporally overlapping motions: disjoint bounds certify the shared window as conflict-free, while unresolved windows are passed to the underlying collision checker. We integrate MR-SPITE into ARC and combine it with VAMP-based collision checking. For 16 Fetch robots, ARC with MR-SPITE achieves a paired median conflict scan speedup of 7.18x and reduces median planning time by 57% relative to the baseline ARC implementation with PRM+VAMP. These results demonstrate that motion-segment bounds complement configuration-level collision acceleration while preserving the behavior of the underlying discretized scanner.

Authors: Marta Markowicz, James Motes, Marco Morales, Nancy Amato

Conflict scanning over synchronized robot paths requires detailed collision checking, potentially across every robot pair at every timestep, and may be repeated many times as conflicts are repaired. We present Multi-Robot SPITE (MR-SPITE), a conservative, motion-segment-based filter for accelerating these scans. MR-SPITE partitions each path into temporal intervals and assigns conservative bounds to each segment. An interval scheduler compares bounds for temporally overlapping motions: disjoint bounds certify the shared window as conflict-free, while unresolved windows are passed to the underlying collision checker. We integrate MR-SPITE into ARC and combine it with VAMP-based collision checking. For 16 Fetch robots, ARC with MR-SPITE achieves a paired median conflict scan speedup of 7.18x and reduces median planning time by 57% relative to the baseline ARC implementation with PRM+VAMP. These results demonstrate that motion-segment bounds complement configuration-level collision acceleration while preserving the behavior of the underlying discretized scanner.

Tuesday, September 22 2026, 00:00

Bichromatic Line-Centers for Point Pairs

Authors: Jaegun Lee, Youjung Bae, Taehoon Ahn, Sang Won Bae, Hee-Kap Ahn

We study the \emph{bichromatic line-center problem} for $n$ pairs of points in the plane. A feasible solution assigns one point from each pair to the red set $R$ and the other to the blue set $B$. The goal is to minimize $\max\{w^\circ(R),\,w^\circ(B)\}$, where $w^\circ(X)$ denotes the minimum width of a strip enclosing $X$; the midlines of the corresponding optimal strips define the line-centers of $R$ and $B$. We consider several variants induced by orientational constraints on line-centers and provide efficient algorithms for each. For one line-center, which consists of computing a minimum-width strip that contains at least one point from each pair, we give an $O(n^2)$-time algorithm. For two line-centers, we obtain an $O(n)$-time algorithm when both are horizontal, and $Θ(n\log n)$-time algorithms when the two centers are parallel or when both orientations are prescribed. When exactly one orientation is prescribed, we give an $O(n^2)$-time algorithm. Finally, for the unrestricted case, we present an $O(n^3\log n)$-time algorithm.

Authors: Jaegun Lee, Youjung Bae, Taehoon Ahn, Sang Won Bae, Hee-Kap Ahn

We study the \emph{bichromatic line-center problem} for $n$ pairs of points in the plane. A feasible solution assigns one point from each pair to the red set $R$ and the other to the blue set $B$. The goal is to minimize $\max\{w^\circ(R),\,w^\circ(B)\}$, where $w^\circ(X)$ denotes the minimum width of a strip enclosing $X$; the midlines of the corresponding optimal strips define the line-centers of $R$ and $B$. We consider several variants induced by orientational constraints on line-centers and provide efficient algorithms for each. For one line-center, which consists of computing a minimum-width strip that contains at least one point from each pair, we give an $O(n^2)$-time algorithm. For two line-centers, we obtain an $O(n)$-time algorithm when both are horizontal, and $Θ(n\log n)$-time algorithms when the two centers are parallel or when both orientations are prescribed. When exactly one orientation is prescribed, we give an $O(n^2)$-time algorithm. Finally, for the unrestricted case, we present an $O(n^3\log n)$-time algorithm.

Tuesday, September 22 2026, 00:00

Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots

Authors: Animesh Maiti, Prakhar Shukla, Subhash Bhagat

Two groups of autonomous, anonymous, and oblivious mobile robots are deployed in the two-dimensional Euclidean plane, each assigned a distinct task. We study a setting where the two groups must simultaneously solve two conflicting pattern formation problems: the \textit{gathering problem}, where robots gather at a point not known to them a priori, and the \textit{circle formation problem}, where robots occupy distinct positions on the boundary of a circle. Although each robot knows its own task, it cannot identify other members of its group. A prior solution~\cite{Conflict-1} addressed this problem for asynchronous robots having {\it direction-only axis agreement} and {\it global weak multiplicity detection} capability available to all robots in both groups. In contrast, in this work, we consider fully {\it disoriented robots} without any axis agreement or common \textit{chirality}. We study the feasibility of a solution to this problem for {\it disoriented robots}. We propose a distributed algorithm that solves the problem for semi-synchronous disoriented robots with non-rigid movements. Our proposed algorithm assumes global weak multiplicity detection only for the gathering group, while for the circle formation group, it requires local weak multiplicity detection.

Authors: Animesh Maiti, Prakhar Shukla, Subhash Bhagat

Two groups of autonomous, anonymous, and oblivious mobile robots are deployed in the two-dimensional Euclidean plane, each assigned a distinct task. We study a setting where the two groups must simultaneously solve two conflicting pattern formation problems: the \textit{gathering problem}, where robots gather at a point not known to them a priori, and the \textit{circle formation problem}, where robots occupy distinct positions on the boundary of a circle. Although each robot knows its own task, it cannot identify other members of its group. A prior solution~\cite{Conflict-1} addressed this problem for asynchronous robots having {\it direction-only axis agreement} and {\it global weak multiplicity detection} capability available to all robots in both groups. In contrast, in this work, we consider fully {\it disoriented robots} without any axis agreement or common \textit{chirality}. We study the feasibility of a solution to this problem for {\it disoriented robots}. We propose a distributed algorithm that solves the problem for semi-synchronous disoriented robots with non-rigid movements. Our proposed algorithm assumes global weak multiplicity detection only for the gathering group, while for the circle formation group, it requires local weak multiplicity detection.

Tuesday, September 22 2026, 00:00

Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria

Authors: Ioannis Anagnostides, Weiqiang Zheng

A (coarse) correlated equilibrium (CE) is information-value-free (IVF) if a player can match the payoff obtained from recommendations by committing to a fixed action. Motivated by the problem of regulating algorithmic collusion, this refinement was introduced by Hartline, Wang, and Zhang [EC'26], who showed that it can be computed in polynomial time in explicitly represented normal-form game. In this paper, we examine the complexity of IVF(C)CEs in succinct games, which model more realistic strategic interactions that feature either many players or exponentially many pure strategies. We first show that computing an information-value-free CE is PPAD-complete in many-player polymatrix games or two-player Bayesian games, even when the approximation is a constant. We also prove an unconditional exponential query lower bound. Our results establish that IVFCEs are intractable, even in the centralized model, and rule out the existence of any efficient learning dynamics. This significantly strengthens the impossibility result of Hartline, Wang, and Zhang, which concerns a particular class of learning algorithms, and furnishes strong computational critiques of recent regulation on algorithmic collusion. To sidestep these hardness results, we examine the complexity of information-value-free CCE. Certain no-regret algorithms---such as regret matching or FTRL---provide a fully polynomial-time approximation scheme (FPTAS) for this problem. The complexity when the approximation is exponentially small turns out to be nuanced. On the one hand, leveraging no-regret dynamics, we establish membership in $\text{CLS} = \text{PPAD} \cap \text{PLS}$. On the other hand, we show that it is at least as hard as the P-matrix linear complementarity problem, and hence as hard as simple stochastic games. This shows that even IVFCCEs are unlikely to admit a polynomial-time algorithm barring a major breakthrough.

Authors: Ioannis Anagnostides, Weiqiang Zheng

A (coarse) correlated equilibrium (CE) is information-value-free (IVF) if a player can match the payoff obtained from recommendations by committing to a fixed action. Motivated by the problem of regulating algorithmic collusion, this refinement was introduced by Hartline, Wang, and Zhang [EC'26], who showed that it can be computed in polynomial time in explicitly represented normal-form game. In this paper, we examine the complexity of IVF(C)CEs in succinct games, which model more realistic strategic interactions that feature either many players or exponentially many pure strategies. We first show that computing an information-value-free CE is PPAD-complete in many-player polymatrix games or two-player Bayesian games, even when the approximation is a constant. We also prove an unconditional exponential query lower bound. Our results establish that IVFCEs are intractable, even in the centralized model, and rule out the existence of any efficient learning dynamics. This significantly strengthens the impossibility result of Hartline, Wang, and Zhang, which concerns a particular class of learning algorithms, and furnishes strong computational critiques of recent regulation on algorithmic collusion. To sidestep these hardness results, we examine the complexity of information-value-free CCE. Certain no-regret algorithms---such as regret matching or FTRL---provide a fully polynomial-time approximation scheme (FPTAS) for this problem. The complexity when the approximation is exponentially small turns out to be nuanced. On the one hand, leveraging no-regret dynamics, we establish membership in $\text{CLS} = \text{PPAD} \cap \text{PLS}$. On the other hand, we show that it is at least as hard as the P-matrix linear complementarity problem, and hence as hard as simple stochastic games. This shows that even IVFCCEs are unlikely to admit a polynomial-time algorithm barring a major breakthrough.

Tuesday, September 22 2026, 00:00

Moving Geometric Objects to Render Their Intersection Graph Connected or Locally Dense

Authors: Tesshu Hanaka, Nicolás Honorato-Droguett, Hirotaka Ono, Samuel Wolf, Alexander Wolff

In this paper, we study graph editing problems on geometric intersection graphs. For a tuple $\mathcal{S}=(S_1,\dots,S_n)$ of geometric objects in some Euclidean space, let $G_\mathcal{S}$ be their intersection graph. We study the problem of finding a tuple $D=(d_1,\dots,d_n)$ of movement vectors such that the resulting intersection graph $G_{\mathcal{S}+D}$ (after moving, for every $i \in \{1,\dots,n\}$, object $S_i$ by $d_i$) has a predefined property and the total movement distance $|D|$ is minimum. In the weighted version, we are also given a weight vector $w=(w_1,\dots,w_n)$ with positive entries, and the objective is to minimise the total weighted movement distance $|w \cdot D|$. We first consider the property locally dense, which we define as containment of a $k$-clique. Given $n$ weighted intervals, we solve the problem with respect to this property in $O(k^{1/3} n \log^{1+\varepsilon} n)$ time for any $\varepsilon>0$. We then consider $k$-connectivity for $1\le k \le n-1$. Given $n$ unweighted unit intervals, we solve the problem in $O(n^2 \log n)$ time and, for $k=1$, in $O(n\log n)$ time. For $k=1$, we prove strong NP-hardness on intervals of arbitrary length and on weighted unit disks (with only two distinct weights), and weak NP-hardness on weighted intervals (even when lengths equal weights).

Authors: Tesshu Hanaka, Nicolás Honorato-Droguett, Hirotaka Ono, Samuel Wolf, Alexander Wolff

In this paper, we study graph editing problems on geometric intersection graphs. For a tuple $\mathcal{S}=(S_1,\dots,S_n)$ of geometric objects in some Euclidean space, let $G_\mathcal{S}$ be their intersection graph. We study the problem of finding a tuple $D=(d_1,\dots,d_n)$ of movement vectors such that the resulting intersection graph $G_{\mathcal{S}+D}$ (after moving, for every $i \in \{1,\dots,n\}$, object $S_i$ by $d_i$) has a predefined property and the total movement distance $|D|$ is minimum. In the weighted version, we are also given a weight vector $w=(w_1,\dots,w_n)$ with positive entries, and the objective is to minimise the total weighted movement distance $|w \cdot D|$. We first consider the property locally dense, which we define as containment of a $k$-clique. Given $n$ weighted intervals, we solve the problem with respect to this property in $O(k^{1/3} n \log^{1+\varepsilon} n)$ time for any $\varepsilon>0$. We then consider $k$-connectivity for $1\le k \le n-1$. Given $n$ unweighted unit intervals, we solve the problem in $O(n^2 \log n)$ time and, for $k=1$, in $O(n\log n)$ time. For $k=1$, we prove strong NP-hardness on intervals of arbitrary length and on weighted unit disks (with only two distinct weights), and weak NP-hardness on weighted intervals (even when lengths equal weights).

Tuesday, September 22 2026, 00:00

Busy Time Minimization with Preemption, Migration, and One Resource Requirement

Authors: Gruia Calinescu, Mozhengfu Liu

We study the Busy Machine Time with Preemption and Migration and One Resource Requirement problem, motivated by energy minimization in cloud data centers. Given unlimited identical-capacity machines and jobs with release times, deadlines, processing times, and resource requirements, we allow free preemption and migration at integer times and seek to minimize total machine busy time. The problem is NP-hard, and previous results consist of a 2-approximation, 2-competitive algorithm for the case of uniform heights. We obtain a 22/9 < 2.445-approximation algorithm and a 2.5-competitive online algorithm, both running in O(n^2 log n) time. Our methods are based on new non-asymptotic performance bounds for the First Fit Decreasing algorithm for Bin Packing, and a new generalization of Span Minimization, the Huge-Tiny Busy Time problem, for which we present an exact offline algorithm and an optimal (3/2)-competitive deterministic online algorithm.

Authors: Gruia Calinescu, Mozhengfu Liu

We study the Busy Machine Time with Preemption and Migration and One Resource Requirement problem, motivated by energy minimization in cloud data centers. Given unlimited identical-capacity machines and jobs with release times, deadlines, processing times, and resource requirements, we allow free preemption and migration at integer times and seek to minimize total machine busy time. The problem is NP-hard, and previous results consist of a 2-approximation, 2-competitive algorithm for the case of uniform heights. We obtain a 22/9 < 2.445-approximation algorithm and a 2.5-competitive online algorithm, both running in O(n^2 log n) time. Our methods are based on new non-asymptotic performance bounds for the First Fit Decreasing algorithm for Bin Packing, and a new generalization of Span Minimization, the Huge-Tiny Busy Time problem, for which we present an exact offline algorithm and an optimal (3/2)-competitive deterministic online algorithm.

Tuesday, September 22 2026, 00:00

Local Representatives and Shortest Completions for Next-to-Shortest Paths in Directed Graphs

Authors: Shisheng Li

Given a directed graph with positive edge weights and two vertices s,t, a next-to-shortest s-t path is a shortest simple s-t path among those whose length is strictly larger than the shortest-path distance. The problem was introduced by Lalgudi, Papaefthymiou and Potkonjak in 1996; it is NP-hard when zero-weight edges are allowed, and its complexity on positively weighted digraphs remained open for almost three decades until Chen, Wein and Zhang recently gave a polynomial-time algorithm running in O(n^4 m^3 log n) time. We give a substantially faster algorithm within their optimal-middle-segment framework. The core idea is to split the problem into "choosing a prefix" and "completing it". Given a prefix P: s -> A made of shortest-path edges, delete the vertices used by P, forbid leaving A along shortest-path edges, and the best completion is one shortest-path computation. The difficulty lies in choosing P: even for a fixed A, deciding whether some shortest prefix admits a completion is NP-complete. We do not solve these fixed-A subproblems one by one. Fix any globally optimal next-to-shortest path; its middle segment induces a boundary edge x -> c in the shortest-path DAG. For the correct triple (A,B,x), the optimal path certifies c as a feasible next hop, and we prove that every feasible next hop that is not earlier than c in a topological order can be combined with the same middle segment into another globally optimal path. Hence only the feasible next hop of maximum topological index is kept per triple, giving O(n^3) representatives, all generated by a two-dimensional DAG dynamic program with a local reward. The total running time is O(n^3 (m + n log n)), and O(n^3 m) on unweighted graphs. The proof rests on an uncrossing lemma: the last intersection between a reference prefix and the candidate's partner suffix can always be moved strictly earlier, which cannot go on forever.

Authors: Shisheng Li

Given a directed graph with positive edge weights and two vertices s,t, a next-to-shortest s-t path is a shortest simple s-t path among those whose length is strictly larger than the shortest-path distance. The problem was introduced by Lalgudi, Papaefthymiou and Potkonjak in 1996; it is NP-hard when zero-weight edges are allowed, and its complexity on positively weighted digraphs remained open for almost three decades until Chen, Wein and Zhang recently gave a polynomial-time algorithm running in O(n^4 m^3 log n) time. We give a substantially faster algorithm within their optimal-middle-segment framework. The core idea is to split the problem into "choosing a prefix" and "completing it". Given a prefix P: s -> A made of shortest-path edges, delete the vertices used by P, forbid leaving A along shortest-path edges, and the best completion is one shortest-path computation. The difficulty lies in choosing P: even for a fixed A, deciding whether some shortest prefix admits a completion is NP-complete. We do not solve these fixed-A subproblems one by one. Fix any globally optimal next-to-shortest path; its middle segment induces a boundary edge x -> c in the shortest-path DAG. For the correct triple (A,B,x), the optimal path certifies c as a feasible next hop, and we prove that every feasible next hop that is not earlier than c in a topological order can be combined with the same middle segment into another globally optimal path. Hence only the feasible next hop of maximum topological index is kept per triple, giving O(n^3) representatives, all generated by a two-dimensional DAG dynamic program with a local reward. The total running time is O(n^3 (m + n log n)), and O(n^3 m) on unweighted graphs. The proof rests on an uncrossing lemma: the last intersection between a reference prefix and the candidate's partner suffix can always be moved strictly earlier, which cannot go on forever.

Tuesday, September 22 2026, 00:00

Union-Find with Constant-Time Deletions Across the Optimal Worst-Case Tradeoff

Authors: Hanqing Li, Ze Hong

We consider union-find with deletions, where the representation and the cost of a query must depend on the current number of live elements rather than on the number of elements ever created. For every integer parameter $k\ge 2$, we give a linear-space data structure supporting $\mathsf{MakeSet}$ in $O(1)$ worst-case time, $\mathsf{Union}$ in $O(k)$ worst-case time, $\mathsf{Delete}$ in $O(1)$ worst-case time, and $\mathsf{Find}$ in $O\left(1+\frac{\log n}{\log k}\right)$ worst-case time for a set containing $n$ live elements. A deletion is given only an element handle, not the identifier of its current set. The construction separates global rank growth from local deletion repair. A logical set is represented by fewer than $k$ disjoint ranked trees. Equal-level trees are collected without physical linking until $k$ certificates are available, at which point one base-$k$ carry is performed in $O(k)$ time. Each member tree uses a strengthened form of the full/reduced local rebuilding scheme of Ben-Amram and Yoffe. A $q$-ary value argument, with $q=3/2$, couples the local trees to the base-$k$ certificates and yields the stated current-size height bound. A small but essential rule handles high-rank stars, a state that the base-$k$ carry can create but that does not arise directly in the binary-rank construction underlying the earlier local scheme.

Authors: Hanqing Li, Ze Hong

We consider union-find with deletions, where the representation and the cost of a query must depend on the current number of live elements rather than on the number of elements ever created. For every integer parameter $k\ge 2$, we give a linear-space data structure supporting $\mathsf{MakeSet}$ in $O(1)$ worst-case time, $\mathsf{Union}$ in $O(k)$ worst-case time, $\mathsf{Delete}$ in $O(1)$ worst-case time, and $\mathsf{Find}$ in $O\left(1+\frac{\log n}{\log k}\right)$ worst-case time for a set containing $n$ live elements. A deletion is given only an element handle, not the identifier of its current set. The construction separates global rank growth from local deletion repair. A logical set is represented by fewer than $k$ disjoint ranked trees. Equal-level trees are collected without physical linking until $k$ certificates are available, at which point one base-$k$ carry is performed in $O(k)$ time. Each member tree uses a strengthened form of the full/reduced local rebuilding scheme of Ben-Amram and Yoffe. A $q$-ary value argument, with $q=3/2$, couples the local trees to the base-$k$ certificates and yields the stated current-size height bound. A small but essential rule handles high-rank stars, a state that the base-$k$ carry can create but that does not arise directly in the binary-rank construction underlying the earlier local scheme.

Tuesday, September 22 2026, 00:00

Hardness of Online Directed Steiner Network

Authors: Gary Hoppenworth, Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski

In the Directed Steiner Network (DSN) problem we are given a directed graph and a set of demands $(s_i,t_i)$, and asked to find a cheap subgraph connecting each terminal pair. In its online version, the demands arrive online and must be served by buying edges irrevocably. DSN is a fundamental hard problem in network design, heavily studied in both the offline and the online setting. Offline, it has a superpolylogarithmic hardness of approximation. However, offline hardness says nothing about online algorithms, which are computationally unrestricted. It has been an open question whether uncertainty itself (needing to commit to a solution without knowing future demands) rules out polylogarithmic-competitive online algorithms. In this work, we show the first such unconditional, information-theoretic hardness. Namely, we give an $\exp\!\bigl(Ω(\sqrt{\log n})\bigr)$ bound on the competitive ratio, which holds even for randomized algorithms against an oblivious adversary, and on unit-cost DAGs. Our proof uses a novel connection between online network design and algebraic coding theory. We encode requests using a hidden low-degree polynomial, whose past evaluations reveal nothing about future ones. We then use list-recovery bounds to show that an algorithm cannot make cheaply reusable decisions without knowing those future evaluations.

Authors: Gary Hoppenworth, Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski

In the Directed Steiner Network (DSN) problem we are given a directed graph and a set of demands $(s_i,t_i)$, and asked to find a cheap subgraph connecting each terminal pair. In its online version, the demands arrive online and must be served by buying edges irrevocably. DSN is a fundamental hard problem in network design, heavily studied in both the offline and the online setting. Offline, it has a superpolylogarithmic hardness of approximation. However, offline hardness says nothing about online algorithms, which are computationally unrestricted. It has been an open question whether uncertainty itself (needing to commit to a solution without knowing future demands) rules out polylogarithmic-competitive online algorithms. In this work, we show the first such unconditional, information-theoretic hardness. Namely, we give an $\exp\!\bigl(Ω(\sqrt{\log n})\bigr)$ bound on the competitive ratio, which holds even for randomized algorithms against an oblivious adversary, and on unit-cost DAGs. Our proof uses a novel connection between online network design and algebraic coding theory. We encode requests using a hidden low-degree polynomial, whose past evaluations reveal nothing about future ones. We then use list-recovery bounds to show that an algorithm cannot make cheaply reusable decisions without knowing those future evaluations.

Tuesday, September 22 2026, 00:00

When Shall We $k$ Meet Again? Tight Algorithms for Diameter and Radius under the Meet Distance

Authors: Yael Kirkpatrick, John Kuszmaul, Merey Temirzinova, Virginia Vassilevska Williams

Finding an optimal meeting point for a collection of agents on a directed graph is a classical problem studied in the context of network analysis, operations research and computational geometry. In this work, we use the two objectives of optimal meeting points examined in the literature to study two notions of meet-distance: $d^{\max}(u,v)$, the minimum over all meeting points $w$ of $\max(d(u,w), d(v,w))$; and $d^+(u,v)$, the minimum over all meeting points of $d(u,w) + d(v,w)$. These values measure the minimum time and minimum total distance required for two agents to meet. We initiate the fine-grained study of fundamental graph parameters under the two notions of meet-distance, namely the diameter, radius and eccentricities. For general directed graphs, we give an $\tilde{O}(m\sqrt{n})$ time algorithm for computing a 2-approximation to both notions of meet-diameter and show that this result is optimal under SETH. In contrast, we show that such a result is unattainable for the meet-radius as any finite approximation requires quadratic time under the Hitting Set Conjecture. For directed acyclic graphs, we obtain stronger results. We compute the meet$^{\max}$-diameter exactly in linear time and give a linear-time $2$-approximation for the meet$^{+}$-diameter. We complement the latter with a quadratic-time lower bound for any $(3/2-\varepsilon)$-approximation under SETH, yielding a separation between the two meet-distance objectives. Finally, we study the generalized meet-distance of $k$-tuples of vertices. For every positive integer $\ell$, we reduce the problem of $\ell$-approximating the $k$-point meet-diameter to computing an exact meet-diameter on smaller tuples, obtaining an $\ell$-approximation in time \[ O\!\left( mn+ \ell \left\lceil k^{1/\ell}\right\rceil n^{\left\lceil k^{1/\ell}\right\rceil+1} \right). \]

Authors: Yael Kirkpatrick, John Kuszmaul, Merey Temirzinova, Virginia Vassilevska Williams

Finding an optimal meeting point for a collection of agents on a directed graph is a classical problem studied in the context of network analysis, operations research and computational geometry. In this work, we use the two objectives of optimal meeting points examined in the literature to study two notions of meet-distance: $d^{\max}(u,v)$, the minimum over all meeting points $w$ of $\max(d(u,w), d(v,w))$; and $d^+(u,v)$, the minimum over all meeting points of $d(u,w) + d(v,w)$. These values measure the minimum time and minimum total distance required for two agents to meet. We initiate the fine-grained study of fundamental graph parameters under the two notions of meet-distance, namely the diameter, radius and eccentricities. For general directed graphs, we give an $\tilde{O}(m\sqrt{n})$ time algorithm for computing a 2-approximation to both notions of meet-diameter and show that this result is optimal under SETH. In contrast, we show that such a result is unattainable for the meet-radius as any finite approximation requires quadratic time under the Hitting Set Conjecture. For directed acyclic graphs, we obtain stronger results. We compute the meet$^{\max}$-diameter exactly in linear time and give a linear-time $2$-approximation for the meet$^{+}$-diameter. We complement the latter with a quadratic-time lower bound for any $(3/2-\varepsilon)$-approximation under SETH, yielding a separation between the two meet-distance objectives. Finally, we study the generalized meet-distance of $k$-tuples of vertices. For every positive integer $\ell$, we reduce the problem of $\ell$-approximating the $k$-point meet-diameter to computing an exact meet-diameter on smaller tuples, obtaining an $\ell$-approximation in time \[ O\!\left( mn+ \ell \left\lceil k^{1/\ell}\right\rceil n^{\left\lceil k^{1/\ell}\right\rceil+1} \right). \]

Tuesday, September 22 2026, 00:00

The Nelson-Nguyen Conjecture via Mean-to-Moments Concentration

Authors: Tung Mai, Anup Rao

An oblivious subspace embedding (OSE) is a distribution over matrices that approximately preserves the squared Euclidean norm of every vector in any fixed low-dimensional subspace. We prove the Nelson-Nguyen conjecture: for every $0 < δ< 1$, there exists a distribution that gives an OSE with embedding dimension $O((d + \log(1/δ))/\varepsilon^2)$ and column sparsity $s = O(\log(d/δ)/\varepsilon)$, with failure probability at most $δ$. We first bound the mean spectral error using a trace-moment argument and then upgrade this bound to the desired high-probability guarantee using concentration and resampling. ChatGPT-5.6-Pro was used in proving and writing the results of this manuscript.

Authors: Tung Mai, Anup Rao

An oblivious subspace embedding (OSE) is a distribution over matrices that approximately preserves the squared Euclidean norm of every vector in any fixed low-dimensional subspace. We prove the Nelson-Nguyen conjecture: for every $0 < δ< 1$, there exists a distribution that gives an OSE with embedding dimension $O((d + \log(1/δ))/\varepsilon^2)$ and column sparsity $s = O(\log(d/δ)/\varepsilon)$, with failure probability at most $δ$. We first bound the mean spectral error using a trace-moment argument and then upgrade this bound to the desired high-probability guarantee using concentration and resampling. ChatGPT-5.6-Pro was used in proving and writing the results of this manuscript.

Tuesday, September 22 2026, 00:00

A Fixed-Parameter Algorithm for 4-Block Integer Programming

Authors: Klaus Jansen, Felix Ohnesorge, Corinna Wambsganz

We give a fixed parameter tractable (FPT) algorithm with running time $f(k,Δ)\cdot {|I|}^{O(1)}$ for integer linear programs with 4-block structure, parameterized by the maximum block dimension $k$ and the largest absolute matrix entry $Δ$. This result resolves a long-standing open question in parameterized complexity, and answers a conjecture by Eisenbrand and Rothvoss (2026) in the positive. This result has several implications for other block-structured integer programming models, including 3-block, mixed fracture number, and special cases of 4-block programs with large entries outside of the diagonal. Important tools for this algorithm are structural properties of generalized $n$-fold integer programs shown by Ligthart~(2026) and an algorithm by Veselov et al.~(2020) for optimizing discrete convic functions.

Authors: Klaus Jansen, Felix Ohnesorge, Corinna Wambsganz

We give a fixed parameter tractable (FPT) algorithm with running time $f(k,Δ)\cdot {|I|}^{O(1)}$ for integer linear programs with 4-block structure, parameterized by the maximum block dimension $k$ and the largest absolute matrix entry $Δ$. This result resolves a long-standing open question in parameterized complexity, and answers a conjecture by Eisenbrand and Rothvoss (2026) in the positive. This result has several implications for other block-structured integer programming models, including 3-block, mixed fracture number, and special cases of 4-block programs with large entries outside of the diagonal. Important tools for this algorithm are structural properties of generalized $n$-fold integer programs shown by Ligthart~(2026) and an algorithm by Veselov et al.~(2020) for optimizing discrete convic functions.

Tuesday, September 22 2026, 00:00

The Facility Advantage in the One-Round Discrete Voronoi Game on a Line

Authors: Tamal Maharaj

In the one-round discrete Voronoi game a multiset $V$ of $n$ voters on a line is given; player P places $k$ facilities, player Q then places $\ell$, and each voter is won by the nearer facility, ties going to P. P wins if it keeps at least $n/2$ voters. In the vocabulary of competitive location this is the absolute $(\ell|k)$-centroid problem on a path with unit demands, and the responder's problem is the $(\ell|X_k)$-medianoid, whose closed form on a path -- the sum of the $\ell$ largest of at most $2k$ explicit marginals -- is due to Spoerhase and Wirth. We record this structure, with complete proofs, and draw two consequences that we believe are new. First, we compute the value of the game against a single responding facility, $Γ_{k,1}(V)$, together with an optimal strategy for P, in $O(n\log n)$ time for arbitrary positive real demands and every $k$. This improves the $O(kn\log^2 n)$ bound of Lazar and Tamir for the absolute $(1|k)$-centroid on a path. Second, we study the facility advantage $k^*(\ell)$, the least $k$ for which P wins every instance against $\ell$ facilities. We prove $k^*(\ell)\le 2\ell-1$, exhibit instances proving $k^*(\ell)\ge\ell+1$ for $2\le\ell\le6$ (an exact, computer-assisted proof resting on a half-integer discretisation), determine $k^*(1)=1$ and $k^*(2)=3$, and show that on uniform instances $k=\ell$ already suffices, so the extremal instances are weighted and Q wins them by a single voter. We conjecture $k^*(\ell)=\ell+1$ for all $\ell\ge2$.

Authors: Tamal Maharaj

In the one-round discrete Voronoi game a multiset $V$ of $n$ voters on a line is given; player P places $k$ facilities, player Q then places $\ell$, and each voter is won by the nearer facility, ties going to P. P wins if it keeps at least $n/2$ voters. In the vocabulary of competitive location this is the absolute $(\ell|k)$-centroid problem on a path with unit demands, and the responder's problem is the $(\ell|X_k)$-medianoid, whose closed form on a path -- the sum of the $\ell$ largest of at most $2k$ explicit marginals -- is due to Spoerhase and Wirth. We record this structure, with complete proofs, and draw two consequences that we believe are new. First, we compute the value of the game against a single responding facility, $Γ_{k,1}(V)$, together with an optimal strategy for P, in $O(n\log n)$ time for arbitrary positive real demands and every $k$. This improves the $O(kn\log^2 n)$ bound of Lazar and Tamir for the absolute $(1|k)$-centroid on a path. Second, we study the facility advantage $k^*(\ell)$, the least $k$ for which P wins every instance against $\ell$ facilities. We prove $k^*(\ell)\le 2\ell-1$, exhibit instances proving $k^*(\ell)\ge\ell+1$ for $2\le\ell\le6$ (an exact, computer-assisted proof resting on a half-integer discretisation), determine $k^*(1)=1$ and $k^*(2)=3$, and show that on uniform instances $k=\ell$ already suffices, so the extremal instances are weighted and Q wins them by a single voter. We conjecture $k^*(\ell)=\ell+1$ for all $\ell\ge2$.

Tuesday, September 22 2026, 00:00

Witness Set in Weak Visibility Polygons is Polynomial-Time Solvable

Authors: Udvas Das, Shouvik Mondal, Sasanka Roy

In the classical Art Gallery Problem (AGP), guards are placed in a polygon so that together they see every point. The Witness Set Problem (WSP), introduced by Amit, Mitchell, and Packer, is a natural dual to the AGP. In this paper, we study the WSP in weak visibility polygons (WVPs), the simple polygons in which every point is seen from some point of one fixed edge. A witness set is a set of points whose visibility regions are pairwise disjoint, so that no single guard sees two of them. A maximum witness set, therefore, lower-bounds the guard number. Exact polynomial-time algorithms for the WSP are known only for monotone mountains, a proper subclass of WVPs. We give the first exact polynomial-time algorithms for the WSP in WVPs, in two settings. In the Discrete Witness Set Problem (DiscWSP), the witnesses come from a given set of $m$ points, and we find a maximum witness subset in $O(n + m \log(n+m))$ time on an $n$-vertex polygon. The algorithm rests on a structural fact: the visibility intersection graph of a WVP, in which two points are adjacent if their visibility regions intersect, is a trapezoid graph, that is, an intersection graph of trapezoids between two parallel lines. Moreover, the class of these graphs properly contains the interval graphs and the permutation graphs, which may be of independent interest in graph theory. We also prove an $Ω(n \log n)$ lower bound in the algebraic decision-tree model for instances with $m = Θ(n)$, so our algorithm for DiscWSP is optimum. In the Continuous Witness Set Problem (ContWSP), a witness may be any point of the polygon, and we give an exact algorithm running in $O(n \log n + ρ^{2}(n + ρ^{2}))$ time, where $ρ$ is the number of reflex vertices.

Authors: Udvas Das, Shouvik Mondal, Sasanka Roy

In the classical Art Gallery Problem (AGP), guards are placed in a polygon so that together they see every point. The Witness Set Problem (WSP), introduced by Amit, Mitchell, and Packer, is a natural dual to the AGP. In this paper, we study the WSP in weak visibility polygons (WVPs), the simple polygons in which every point is seen from some point of one fixed edge. A witness set is a set of points whose visibility regions are pairwise disjoint, so that no single guard sees two of them. A maximum witness set, therefore, lower-bounds the guard number. Exact polynomial-time algorithms for the WSP are known only for monotone mountains, a proper subclass of WVPs. We give the first exact polynomial-time algorithms for the WSP in WVPs, in two settings. In the Discrete Witness Set Problem (DiscWSP), the witnesses come from a given set of $m$ points, and we find a maximum witness subset in $O(n + m \log(n+m))$ time on an $n$-vertex polygon. The algorithm rests on a structural fact: the visibility intersection graph of a WVP, in which two points are adjacent if their visibility regions intersect, is a trapezoid graph, that is, an intersection graph of trapezoids between two parallel lines. Moreover, the class of these graphs properly contains the interval graphs and the permutation graphs, which may be of independent interest in graph theory. We also prove an $Ω(n \log n)$ lower bound in the algebraic decision-tree model for instances with $m = Θ(n)$, so our algorithm for DiscWSP is optimum. In the Continuous Witness Set Problem (ContWSP), a witness may be any point of the polygon, and we give an exact algorithm running in $O(n \log n + ρ^{2}(n + ρ^{2}))$ time, where $ρ$ is the number of reflex vertices.

Tuesday, September 22 2026, 00:00

Approximating Prize-Collecting TSP below 1.556

Authors: Hong Li

The prize-collecting traveling salesperson problem is a variant of the metric traveling salesperson problem in which vertices may be left unvisited by paying their associated penalties. The objective is to minimize the length of the tour plus the total penalty of the unvisited vertices. Blauth, Klein, and Nägele gave the previously best-known LP-relative $1.599$-approximation. We show that a simpler version of their algorithm, obtained by omitting the splitting-off preprocessing before the tree decomposition, has an LP-relative approximation ratio of $1.555761$. The improvement comes from a stronger analysis of the parity-correction step.

Authors: Hong Li

The prize-collecting traveling salesperson problem is a variant of the metric traveling salesperson problem in which vertices may be left unvisited by paying their associated penalties. The objective is to minimize the length of the tour plus the total penalty of the unvisited vertices. Blauth, Klein, and Nägele gave the previously best-known LP-relative $1.599$-approximation. We show that a simpler version of their algorithm, obtained by omitting the splitting-off preprocessing before the tree decomposition, has an LP-relative approximation ratio of $1.555761$. The improvement comes from a stronger analysis of the parity-correction step.

Tuesday, September 22 2026, 00:00

A Proof of the Most Informative Boolean Function Conjecture

Authors: Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni, Chandra Nair, David P. Woodruff

Let $X$ be uniform on $\{-1,1\}^n$, let $Y$ be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability $p$, and let $g:\{-1,1\}^n\to\{0,1\}$ be a Boolean function. We give a computer-assisted proof of the Courtade--Kumar conjecture $I(g(X);Y)\le1-H_2(p)$, where $H_2$ is binary entropy, with equality attained by dictator functions. The present work builds on the differential-equation method, itself a limiting form of the auxiliary-receiver approach in network information theory using a continuum of degraded receivers. The proof proceeds from a local inequality to a dimension-independent bound on entropy production. Differentiation along the Boolean noise semigroup expresses entropy production as an average of edge costs. The key estimate is therefore an unrestricted Bellman inequality with two mean constraints and two entropy constraints, allowing arbitrary couplings of the edge variables. This paper and its supplement provide the proofs and computational verification records. The document is lengthy because it is designed to be entirely self-contained, deriving all proofs from first principles and reproducing the proofs of cited results. The supplementary material supporting the computer-assisted parts of the proof are available online.

Authors: Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni, Chandra Nair, David P. Woodruff

Let $X$ be uniform on $\{-1,1\}^n$, let $Y$ be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability $p$, and let $g:\{-1,1\}^n\to\{0,1\}$ be a Boolean function. We give a computer-assisted proof of the Courtade--Kumar conjecture $I(g(X);Y)\le1-H_2(p)$, where $H_2$ is binary entropy, with equality attained by dictator functions. The present work builds on the differential-equation method, itself a limiting form of the auxiliary-receiver approach in network information theory using a continuum of degraded receivers. The proof proceeds from a local inequality to a dimension-independent bound on entropy production. Differentiation along the Boolean noise semigroup expresses entropy production as an average of edge costs. The key estimate is therefore an unrestricted Bellman inequality with two mean constraints and two entropy constraints, allowing arbitrary couplings of the edge variables. This paper and its supplement provide the proofs and computational verification records. The document is lengthy because it is designed to be entirely self-contained, deriving all proofs from first principles and reproducing the proofs of cited results. The supplementary material supporting the computer-assisted parts of the proof are available online.

Tuesday, September 22 2026, 00:00

Parameter-Free Triangle Counting

Authors: Asaf Etgar, Anna Gilbert, Quanquan Liu, Andrew McGregor

Given an undirected, unweighted graph $G = (V,E)$ with $n$ vertices and $m$ edges, the triangle counting problem seeks the number of three-cycles in it. Triangle and subgraph counting are classical problems in graph algorithms, central to applications such as community detection, computing the clustering coefficient, motif discovery in protein networks, and social network analysis. In many of these applications, the graph datasets are so voluminous that we model them as streams of updates to an underlying graph. There are a number of foundational results for streaming triangle counting, both theoretical and practical. There is, however, one major drawback to all previous sublinear-space algorithms: to achieve both a constant factor approximation and the sublinear space guarantees, one needs to know a priori a constant factor approximation of the triangle count $T$, an inherently circular requirement. We initiate the study of parameter-free streaming triangle counting, without any a priori knowledge of $T$ or any quantities depending on $T$, provided $m$, the length of the stream. We describe a family of $O(p)$ pass parameter-free triangle counting algorithms that guarantee a mixed multiplicative and additive approximation of $T$ and use $\widetilde{O}(\frac{m+T}{\sqrt{T}})$ expected space. Moreover, this family leads to an $O(\log\log(n))$ pass algorithm that gives a $(1+\eps)$ multiplicative approximation of $T$ with the same space complexity. These algorithms rely on the notion of a \emph{verified} parametrized algorithm: an algorithm parametrized by $τ$ that either provides an approximation of $T$ when $τ\le T$, or declares that $T < τ$. Furthermore, we prove a lower bound: any parameter-free algorithm that provides a multiplicative approximation for all values of $T$ must use $Θ(m)$ space, even on streams where the triangle count is moderately large.

Authors: Asaf Etgar, Anna Gilbert, Quanquan Liu, Andrew McGregor

Given an undirected, unweighted graph $G = (V,E)$ with $n$ vertices and $m$ edges, the triangle counting problem seeks the number of three-cycles in it. Triangle and subgraph counting are classical problems in graph algorithms, central to applications such as community detection, computing the clustering coefficient, motif discovery in protein networks, and social network analysis. In many of these applications, the graph datasets are so voluminous that we model them as streams of updates to an underlying graph. There are a number of foundational results for streaming triangle counting, both theoretical and practical. There is, however, one major drawback to all previous sublinear-space algorithms: to achieve both a constant factor approximation and the sublinear space guarantees, one needs to know a priori a constant factor approximation of the triangle count $T$, an inherently circular requirement. We initiate the study of parameter-free streaming triangle counting, without any a priori knowledge of $T$ or any quantities depending on $T$, provided $m$, the length of the stream. We describe a family of $O(p)$ pass parameter-free triangle counting algorithms that guarantee a mixed multiplicative and additive approximation of $T$ and use $\widetilde{O}(\frac{m+T}{\sqrt{T}})$ expected space. Moreover, this family leads to an $O(\log\log(n))$ pass algorithm that gives a $(1+\eps)$ multiplicative approximation of $T$ with the same space complexity. These algorithms rely on the notion of a \emph{verified} parametrized algorithm: an algorithm parametrized by $τ$ that either provides an approximation of $T$ when $τ\le T$, or declares that $T < τ$. Furthermore, we prove a lower bound: any parameter-free algorithm that provides a multiplicative approximation for all values of $T$ must use $Θ(m)$ space, even on streams where the triangle count is moderately large.

Tuesday, September 22 2026, 00:00

FPT Isomorphism Test for $F$-Free Tournaments

Authors: Daniel Neuen

We show that isomorphism of $F$-free tournaments can be solved in FPT time $f(k) \cdot n^{O(1)}$, where $k$ denotes the size of $F$, and $n$ denotes the size of the input tournaments. Our result extends on a previous FPT isomorphism test for tournaments of bounded twin-width [Grohe, Neuen 2024], as well as XP isomorphism tests parameterized by the VC dimension or the chromatic number [Raßmann, Schweitzer 2026]. It also implies that every non-trivial hereditary class of tournaments admits a polynomial-time isomorphism test. Our algorithm builds on a novel combination of spectral, geometric, combinatorial and group-theoretic tools.

Authors: Daniel Neuen

We show that isomorphism of $F$-free tournaments can be solved in FPT time $f(k) \cdot n^{O(1)}$, where $k$ denotes the size of $F$, and $n$ denotes the size of the input tournaments. Our result extends on a previous FPT isomorphism test for tournaments of bounded twin-width [Grohe, Neuen 2024], as well as XP isomorphism tests parameterized by the VC dimension or the chromatic number [Raßmann, Schweitzer 2026]. It also implies that every non-trivial hereditary class of tournaments admits a polynomial-time isomorphism test. Our algorithm builds on a novel combination of spectral, geometric, combinatorial and group-theoretic tools.

Tuesday, September 22 2026, 00:00

Improved polynomial-time algorithms for detecting and recovering planted $Θ(\sqrt{n})$-cliques

Authors: Dmitriy Kunisky, Songtao Mao

In the planted clique problem, one observes either an Erdős--Rényi graph on $n$ vertices or such a graph with a clique added to $k = k(n)$ vertices, and seeks to detect or recover the clique. It is widely believed that $k = Θ(\sqrt{n})$ is the smallest clique size for which polynomial-time algorithms exist for these tasks. We develop new algorithms in this regime using color-coding to estimate signed subgraph counts, further accelerated with fast matrix multiplication. We first show that, for each $t \geq 1$, for $c(t)$ a constant associated to the order of growth of the number of connected graphs of treewidth at most $t$, cliques of size $k = λ\sqrt{n}$ planted in a random location with $λ> 1 / \sqrt{c(t)}$ can be detected and recovered in time $n^{t + 1 + o(1)}$. For instance, since $c(1) = e$, this recovers by counting signed trees the performance of the $\widetilde{O}(n^2)$-time message-passing algorithm of Deshpande--Montanari (2015) that succeeds when $λ> 1 / \sqrt{e} \approx 0.6066$. For $t \geq 3$, the exact value of $c(t)$ is not known, but lower bounds on it give a hierarchy of slower polynomial-time algorithms that succeed for smaller $λ$. We further show that the above algorithm for $t = 2$ can be implemented in time $n^{ω+ o(1)}$ for $ω$ the constant of square matrix multiplication and succeeds when $λ> 0.3320$; under the folklore conjecture that $ω= 2$, this runs in the nearly-linear time of the algorithm of Deshpande--Montanari while finding smaller cliques. Second, we show that the above algorithm for $t = 1$ can be combined with the boosting scheme of Alon--Krivelevich--Sudakov (1998) using rectangular matrix multiplication, giving improved runtimes for smaller $λ$. Taken together, our results achieve the best known tradeoff between runtime and signal strength $λ$.

Authors: Dmitriy Kunisky, Songtao Mao

In the planted clique problem, one observes either an Erdős--Rényi graph on $n$ vertices or such a graph with a clique added to $k = k(n)$ vertices, and seeks to detect or recover the clique. It is widely believed that $k = Θ(\sqrt{n})$ is the smallest clique size for which polynomial-time algorithms exist for these tasks. We develop new algorithms in this regime using color-coding to estimate signed subgraph counts, further accelerated with fast matrix multiplication. We first show that, for each $t \geq 1$, for $c(t)$ a constant associated to the order of growth of the number of connected graphs of treewidth at most $t$, cliques of size $k = λ\sqrt{n}$ planted in a random location with $λ> 1 / \sqrt{c(t)}$ can be detected and recovered in time $n^{t + 1 + o(1)}$. For instance, since $c(1) = e$, this recovers by counting signed trees the performance of the $\widetilde{O}(n^2)$-time message-passing algorithm of Deshpande--Montanari (2015) that succeeds when $λ> 1 / \sqrt{e} \approx 0.6066$. For $t \geq 3$, the exact value of $c(t)$ is not known, but lower bounds on it give a hierarchy of slower polynomial-time algorithms that succeed for smaller $λ$. We further show that the above algorithm for $t = 2$ can be implemented in time $n^{ω+ o(1)}$ for $ω$ the constant of square matrix multiplication and succeeds when $λ> 0.3320$; under the folklore conjecture that $ω= 2$, this runs in the nearly-linear time of the algorithm of Deshpande--Montanari while finding smaller cliques. Second, we show that the above algorithm for $t = 1$ can be combined with the boosting scheme of Alon--Krivelevich--Sudakov (1998) using rectangular matrix multiplication, giving improved runtimes for smaller $λ$. Taken together, our results achieve the best known tradeoff between runtime and signal strength $λ$.

Tuesday, September 22 2026, 00:00

An Incremental Algorithm for Checking the Possibility of Braess Paradox in Dynamic Nets

Authors: Dario Fiorenza, Daniele Gorla, Ivano Salvo

Braess paradox is a well-known phenomenon that originates when latency at Wardrop equilibrium in traffic networks decreases because of removing edges. The possibility of having the paradox was called vulnerability by Roughgarden in 2006 and was characterized later on by graph-theoretical notions, both for undirected and for directed graphs. In this paper we provide an algorithm for the incremental case of checking vulnerability for dynamically evolving graphs. The crucial idea to keep the amortized cost linear for every edge addition is that we do not need to run the vulnerability algorithm on the whole graph, but only on a well-identified subgraph, determined by the edge that we are adding. Overall, to add m edges, we pay a cost of O(m2); this aligns with the O(m2) cost of the state-of-the-art static algorithm for vulnerability.

Authors: Dario Fiorenza, Daniele Gorla, Ivano Salvo

Braess paradox is a well-known phenomenon that originates when latency at Wardrop equilibrium in traffic networks decreases because of removing edges. The possibility of having the paradox was called vulnerability by Roughgarden in 2006 and was characterized later on by graph-theoretical notions, both for undirected and for directed graphs. In this paper we provide an algorithm for the incremental case of checking vulnerability for dynamically evolving graphs. The crucial idea to keep the amortized cost linear for every edge addition is that we do not need to run the vulnerability algorithm on the whole graph, but only on a well-identified subgraph, determined by the edge that we are adding. Overall, to add m edges, we pay a cost of O(m2); this aligns with the O(m2) cost of the state-of-the-art static algorithm for vulnerability.

Tuesday, September 22 2026, 00:00

Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number

Authors: Andrea Munaro

We establish a strongly sublinear counterpart of a recent result of Chudnovsky, E S, and Lokshtanov (arXiv 2025) on treewidth and tree-independence number. Namely, we prove that a hereditary graph class has strongly sublinear tree-independence number if and only if, for every fixed clique bound, its graphs of bounded clique number have strongly sublinear treewidth. In fact, this is part of a broader equivalence theorem. For hereditary classes, these conditions are also equivalent to having clique-dependent polynomial expansion, to admitting balanced separators whose size is bounded by $Kω(G)^s |V(G)|^{1-β}$ for fixed $K,s,β>0$, and to admitting balanced clique-based separators of strongly sublinear size (equivalently, weight). Thus, we show that all these properties, which arose independently in the study of subexponential-time exact algorithms and polynomial-time approximation schemes, in fact describe the same hereditary graph classes. As a consequence of our equivalence theorem, we also show that every hereditary class $\mathcal C$ with strongly sublinear tree-independence number admits a subexponential-time algorithm that, given $G\in\mathcal C$, computes a tree decomposition of $G$ with strongly sublinear independence number.

Authors: Andrea Munaro

We establish a strongly sublinear counterpart of a recent result of Chudnovsky, E S, and Lokshtanov (arXiv 2025) on treewidth and tree-independence number. Namely, we prove that a hereditary graph class has strongly sublinear tree-independence number if and only if, for every fixed clique bound, its graphs of bounded clique number have strongly sublinear treewidth. In fact, this is part of a broader equivalence theorem. For hereditary classes, these conditions are also equivalent to having clique-dependent polynomial expansion, to admitting balanced separators whose size is bounded by $Kω(G)^s |V(G)|^{1-β}$ for fixed $K,s,β>0$, and to admitting balanced clique-based separators of strongly sublinear size (equivalently, weight). Thus, we show that all these properties, which arose independently in the study of subexponential-time exact algorithms and polynomial-time approximation schemes, in fact describe the same hereditary graph classes. As a consequence of our equivalence theorem, we also show that every hereditary class $\mathcal C$ with strongly sublinear tree-independence number admits a subexponential-time algorithm that, given $G\in\mathcal C$, computes a tree decomposition of $G$ with strongly sublinear independence number.

Tuesday, September 22 2026, 00:00

Vertex Cover Interdiction in Bipartite Graphs

Authors: Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

In the vertex cover interdiction problem, we are given an undirected graph $G=(V,E)$, two integers $t$ and $k$ and a vertex subset $B\subseteq V$, and we are asked to find a set $X \subseteq B$ with $|X|\leq t$ such that $X$ hits (i.e., intersects) all the vertex covers of $G$ of size at most $k$. Recently, Grüne and Wulf proved that the problem is $Σ_2^p$-complete. However, their reduction relied on the fact that the vertex cover problem is NP-complete. This, in turn, means that we do not know the complexity status of the vertex cover interdiction problem when the input graph is restricted to a bipartite graph since the vertex cover problem can be solved in polynomial time for bipartite graphs. One of our main results shows that the vertex cover interdiction problem is NP-complete for bipartite graphs. In contrast, when $k$ is restricted to the minimum vertex cover size, i.e., we are only required to hit all the minimum vertex covers, we show that the vertex cover interdiction problem can be solved in polynomial time for bipartite graphs. This motivates us to study the parameterized complexity of the vertex cover interdiction problem for bipartite graphs when the difference of $k$ and the minimum vertex cover size is taken as a parameter. With this parameter, we show that the problem is $\mathrm{W}[1]$-hard, but can be solved in polynomial time when the parameter is constant (i.e., in XP time). We also show that the problem is fixed-parameter tractable when parameterized by $k$.

Authors: Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

In the vertex cover interdiction problem, we are given an undirected graph $G=(V,E)$, two integers $t$ and $k$ and a vertex subset $B\subseteq V$, and we are asked to find a set $X \subseteq B$ with $|X|\leq t$ such that $X$ hits (i.e., intersects) all the vertex covers of $G$ of size at most $k$. Recently, Grüne and Wulf proved that the problem is $Σ_2^p$-complete. However, their reduction relied on the fact that the vertex cover problem is NP-complete. This, in turn, means that we do not know the complexity status of the vertex cover interdiction problem when the input graph is restricted to a bipartite graph since the vertex cover problem can be solved in polynomial time for bipartite graphs. One of our main results shows that the vertex cover interdiction problem is NP-complete for bipartite graphs. In contrast, when $k$ is restricted to the minimum vertex cover size, i.e., we are only required to hit all the minimum vertex covers, we show that the vertex cover interdiction problem can be solved in polynomial time for bipartite graphs. This motivates us to study the parameterized complexity of the vertex cover interdiction problem for bipartite graphs when the difference of $k$ and the minimum vertex cover size is taken as a parameter. With this parameter, we show that the problem is $\mathrm{W}[1]$-hard, but can be solved in polynomial time when the parameter is constant (i.e., in XP time). We also show that the problem is fixed-parameter tractable when parameterized by $k$.

Tuesday, September 22 2026, 00:00

Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids

Authors: Shi Fu, Youming Qiao, Dacheng Tao, Zongqi Wan, Qixin Zhang

Over the past decade, a growing body of research has shown that $γ$-weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural network pruning, and video summarization. Despite its prevalence, maximizing a $γ$-weakly submodular function subject to a general matroid constraint remains challenging. To date, the only known approximation guarantee is the conservative $(1+1/γ)^{-2}$ factor established by \citet{chen2018weakly}. To improve upon this result, this paper proposes a novel algorithm called \MGPE, which repeatedly performs maximum-gain local exchanges through careful control of a non-homogeneous Poisson clock, and proves that this \MGPE\ can attain an approximation ratio arbitrarily close to $ρ_γ=1-\left(γ/(2-γ)\right)^{ \frac{γ^2}{2(1-γ)} }$. In sharp contrast to the previous guarantee, our obtained factor $ρ_γ$ not only strictly improves upon $(1+1/γ)^{-2}$ for every $γ\in(0,1]$, but also can asymptotically approach the optimal $(1-1/e)$-approximation for submodular maximization as $γ\to1$. Furthermore, we surprisingly find that when the matroid constraint reduces to a cardinality or the objective satisfies the stronger notion of $α$-weak DR-submodularity, \MGPE\ can automatically recover the tight approximation ratios of $1-e^{-γ}$ and $1-e^{-α}$, respectively. Here, $α\in(0,1]$ denotes the DR ratio.

Authors: Shi Fu, Youming Qiao, Dacheng Tao, Zongqi Wan, Qixin Zhang

Over the past decade, a growing body of research has shown that $γ$-weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural network pruning, and video summarization. Despite its prevalence, maximizing a $γ$-weakly submodular function subject to a general matroid constraint remains challenging. To date, the only known approximation guarantee is the conservative $(1+1/γ)^{-2}$ factor established by \citet{chen2018weakly}. To improve upon this result, this paper proposes a novel algorithm called \MGPE, which repeatedly performs maximum-gain local exchanges through careful control of a non-homogeneous Poisson clock, and proves that this \MGPE\ can attain an approximation ratio arbitrarily close to $ρ_γ=1-\left(γ/(2-γ)\right)^{ \frac{γ^2}{2(1-γ)} }$. In sharp contrast to the previous guarantee, our obtained factor $ρ_γ$ not only strictly improves upon $(1+1/γ)^{-2}$ for every $γ\in(0,1]$, but also can asymptotically approach the optimal $(1-1/e)$-approximation for submodular maximization as $γ\to1$. Furthermore, we surprisingly find that when the matroid constraint reduces to a cardinality or the objective satisfies the stronger notion of $α$-weak DR-submodularity, \MGPE\ can automatically recover the tight approximation ratios of $1-e^{-γ}$ and $1-e^{-α}$, respectively. Here, $α\in(0,1]$ denotes the DR ratio.

Tuesday, September 22 2026, 00:00

On Deterministically Computing Total Variation Distance via Zonotope Compression

Authors: Yucheng Fu

We study deterministic relative approximation of the total variation distance between high-dimensional distributions given by succinct descriptions. We develop an abstract deterministic approximation framework based on representing the total variation distance as a support function of a low-dimensional zonotope. As applications, we obtain FPTASs for several models. Given two mixtures of product distributions over $[q]^n$ with a total of $K$ component distributions, our algorithm approximates their TV-distance within a factor of $1+\varepsilon$ in time $\widetilde O_K(nq(n/\varepsilon)^{2K})$. We also give an FPTAS for mixtures of $n$-step Markov chains over $[q]^n$ with a total of $K$ component distributions, with running time $\widetilde O_K(nq^2(n/\varepsilon)^{2K})$. Finally, for two latent-tree Ising models with the same underlying tree topology, we give an FPTAS for the TV-distance between their leaf marginals in time $O(|V|^{13}\varepsilon^{-12})$.

Authors: Yucheng Fu

We study deterministic relative approximation of the total variation distance between high-dimensional distributions given by succinct descriptions. We develop an abstract deterministic approximation framework based on representing the total variation distance as a support function of a low-dimensional zonotope. As applications, we obtain FPTASs for several models. Given two mixtures of product distributions over $[q]^n$ with a total of $K$ component distributions, our algorithm approximates their TV-distance within a factor of $1+\varepsilon$ in time $\widetilde O_K(nq(n/\varepsilon)^{2K})$. We also give an FPTAS for mixtures of $n$-step Markov chains over $[q]^n$ with a total of $K$ component distributions, with running time $\widetilde O_K(nq^2(n/\varepsilon)^{2K})$. Finally, for two latent-tree Ising models with the same underlying tree topology, we give an FPTAS for the TV-distance between their leaf marginals in time $O(|V|^{13}\varepsilon^{-12})$.

Tuesday, September 22 2026, 00:00

Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata

Authors: Purv Patel, Ajay D. Kshemkalyani

Asynchronous Byzantine Reliable Broadcast (BRB) is a fundamental primitive that guarantees agreement and validity in distributed systems subject to Byzantine faults, but it lacks ordering guarantees. In this paper, we address Byzantine Causal Reliable Broadcast (BCRB), which builds on BRB to enforce causal message ordering. We present a novel BCRB protocol that decouples causal ordering from the BRB layer, achieving constant-size $\mathcal{O}(1)$ message metadata overhead and $\mathcal{O}(n^2)$ communication word complexity as against $\mathcal{O}(n^3)$ communication word complexity of existing protocols; here $n$ is the number of processes. We present two variants of our protocol: a cryptographic version using a threshold encryption scheme and sequence gating, and its non-cryptographic version. In the cryptographic version, senders broadcast ciphertexts immediately, and decryption shares are piggybacked on out-of-band ACKs, preventing early decryption and front-running. In both versions, causal safety is achieved probabilistically. We evaluate the probability of causal safety violations using a random variable path analysis under independent exponential link delay distributions. We show that both variants satisfy liveness and the probability of weak safety violation is bounded by $\mathcal{O}(f^{-3}\cdot\ln^3 f)$, where $f$ is the upper bound on the number of Byzantine processes, and $f < n/3$ and $f=\mathcal{O}(n)$. Further, for the crypto version, we show that the probability of strong safety violation is bounded by $\mathcal{O}(f^{-1} \cdot \ln^2 f)$. We also show how to modify our two protocols to guarantee 100\% weak safety keeping $\mathcal{O}(1)$ message space overhead but with $\mathcal{O}(n^3)$ messages and $\mathcal{O}(n^3)$ communication word complexity.

Authors: Purv Patel, Ajay D. Kshemkalyani

Asynchronous Byzantine Reliable Broadcast (BRB) is a fundamental primitive that guarantees agreement and validity in distributed systems subject to Byzantine faults, but it lacks ordering guarantees. In this paper, we address Byzantine Causal Reliable Broadcast (BCRB), which builds on BRB to enforce causal message ordering. We present a novel BCRB protocol that decouples causal ordering from the BRB layer, achieving constant-size $\mathcal{O}(1)$ message metadata overhead and $\mathcal{O}(n^2)$ communication word complexity as against $\mathcal{O}(n^3)$ communication word complexity of existing protocols; here $n$ is the number of processes. We present two variants of our protocol: a cryptographic version using a threshold encryption scheme and sequence gating, and its non-cryptographic version. In the cryptographic version, senders broadcast ciphertexts immediately, and decryption shares are piggybacked on out-of-band ACKs, preventing early decryption and front-running. In both versions, causal safety is achieved probabilistically. We evaluate the probability of causal safety violations using a random variable path analysis under independent exponential link delay distributions. We show that both variants satisfy liveness and the probability of weak safety violation is bounded by $\mathcal{O}(f^{-3}\cdot\ln^3 f)$, where $f$ is the upper bound on the number of Byzantine processes, and $f < n/3$ and $f=\mathcal{O}(n)$. Further, for the crypto version, we show that the probability of strong safety violation is bounded by $\mathcal{O}(f^{-1} \cdot \ln^2 f)$. We also show how to modify our two protocols to guarantee 100\% weak safety keeping $\mathcal{O}(1)$ message space overhead but with $\mathcal{O}(n^3)$ messages and $\mathcal{O}(n^3)$ communication word complexity.

Tuesday, September 22 2026, 00:00

Optimal Analysis of Greedy for Stochastic Online Euclidean Matching

Authors: Mingwei Yang, Sophie H. Yu

We study Greedy for online metric matching with $n$ servers and $n$ requests sampled independently and uniformly from $[0,1]^d$. Servers are available initially, and Greedy irrevocably matches each arriving request to its closest available server, incurring a cost of their distance. We prove that Greedy has competitive ratio $O(1)$ for every fixed $d\ne2$, and $Θ(\sqrt{\log n})$ for $d=2$. Previously, constant competitiveness was shown for $d = 1$ [BFP23], and no non-trivial results for this setting were known for higher dimensions. Our proof first analyzes Greedy on the flat torus and then transfers the estimates back to the cube.

Authors: Mingwei Yang, Sophie H. Yu

We study Greedy for online metric matching with $n$ servers and $n$ requests sampled independently and uniformly from $[0,1]^d$. Servers are available initially, and Greedy irrevocably matches each arriving request to its closest available server, incurring a cost of their distance. We prove that Greedy has competitive ratio $O(1)$ for every fixed $d\ne2$, and $Θ(\sqrt{\log n})$ for $d=2$. Previously, constant competitiveness was shown for $d = 1$ [BFP23], and no non-trivial results for this setting were known for higher dimensions. Our proof first analyzes Greedy on the flat torus and then transfers the estimates back to the cube.

Tuesday, September 22 2026, 00:00

Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time

Authors: Ali Jadbabaie, Amin Saberi, Suvrit Sra

We prove two main algorithmic results in spectral discrepancy. First, we give a deterministic polynomial-time rounding theorem for rational positive semidefinite matrices of arbitrary rank. The algorithm starts from any rational fractional signing and assigns one sign per original matrix. Its discrepancy is less than $3.37\,\|\sum_i \mathrm{Tr}(A_i)A_i\|^{1/2}$. This yields Kadison--Singer half-partitions with error below $1.69\sqrt{\varepsilon}$, as well as deterministic graph signings that control signed adjacency and signed degrees simultaneously. The proof builds on the spectral-potential method of Ezeunala and Jiang (2026) and introduces a new way to choose rounding directions. We prove polynomial bit complexity for the rounding procedure. Second, we give a Las Vegas algorithm for the Bilu--Linial signing problem on an arbitrary prescribed graph. If $G$ has $n$ vertices and maximum degree $Δ\ge3$, the algorithm terminates almost surely. It uses fewer than $100n^3$ insertion attempts in expectation and returns a signing with $\|A_s\|<2\sqrt{2(Δ-1)}$. For bipartite graphs its one-sided form gives the sharp universal bound $\|A_s\|<2\sqrt{Δ-1}$. The algorithm builds the signing by inserting vertices and recursively deleting and restoring neighbors after rejected insertions. In the analysis, the $\sqrt2$ gap to the Bilu--Linial conjecture comes from a factor of two in the bound for vertex deletions in the two-sided case. On a $d$-regular bipartite Ramanujan base the same signing produces a Ramanujan $2$-lift of that prescribed base.

Authors: Ali Jadbabaie, Amin Saberi, Suvrit Sra

We prove two main algorithmic results in spectral discrepancy. First, we give a deterministic polynomial-time rounding theorem for rational positive semidefinite matrices of arbitrary rank. The algorithm starts from any rational fractional signing and assigns one sign per original matrix. Its discrepancy is less than $3.37\,\|\sum_i \mathrm{Tr}(A_i)A_i\|^{1/2}$. This yields Kadison--Singer half-partitions with error below $1.69\sqrt{\varepsilon}$, as well as deterministic graph signings that control signed adjacency and signed degrees simultaneously. The proof builds on the spectral-potential method of Ezeunala and Jiang (2026) and introduces a new way to choose rounding directions. We prove polynomial bit complexity for the rounding procedure. Second, we give a Las Vegas algorithm for the Bilu--Linial signing problem on an arbitrary prescribed graph. If $G$ has $n$ vertices and maximum degree $Δ\ge3$, the algorithm terminates almost surely. It uses fewer than $100n^3$ insertion attempts in expectation and returns a signing with $\|A_s\|<2\sqrt{2(Δ-1)}$. For bipartite graphs its one-sided form gives the sharp universal bound $\|A_s\|<2\sqrt{Δ-1}$. The algorithm builds the signing by inserting vertices and recursively deleting and restoring neighbors after rejected insertions. In the analysis, the $\sqrt2$ gap to the Bilu--Linial conjecture comes from a factor of two in the bound for vertex deletions in the two-sided case. On a $d$-regular bipartite Ramanujan base the same signing produces a Ramanujan $2$-lift of that prescribed base.

Tuesday, September 22 2026, 00:00

A Simpler and Faster Min-Cost Flow Solver via Min-Ratio Cycles from Distance Oracles

Authors: Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg, Aurelio Sulser

The first almost-linear time maximum and minimum cost flow algorithm of Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022), reduced these flow objectives to a sequence of min-ratio cycle problems. Solving this core primitive requires approximately minimizing the ratio of a linear gradient term and an undirected length term. In Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022) and the subsequent work of Chen-Kyng-Liu-Meierhans-Probst Gutenberg (STOC 2024), intricate data structures were given to solve the min-ratio problem. We show that such a cycle can be extracted directly from the dynamic distance oracle of Kyng-Meierhans-Probst Gutenberg (STOC 2024) using linearity. This simplifies previous algorithms that relied on multiple additional steps to extract the cycle, and can be seen as evidence that solving the min-ratio cycle problem really is all about distances. As a result, we obtain a faster primal maxflow and min-cost flow solver that also extends to incremental graphs.

Authors: Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg, Aurelio Sulser

The first almost-linear time maximum and minimum cost flow algorithm of Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022), reduced these flow objectives to a sequence of min-ratio cycle problems. Solving this core primitive requires approximately minimizing the ratio of a linear gradient term and an undirected length term. In Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022) and the subsequent work of Chen-Kyng-Liu-Meierhans-Probst Gutenberg (STOC 2024), intricate data structures were given to solve the min-ratio problem. We show that such a cycle can be extracted directly from the dynamic distance oracle of Kyng-Meierhans-Probst Gutenberg (STOC 2024) using linearity. This simplifies previous algorithms that relied on multiple additional steps to extract the cycle, and can be seen as evidence that solving the min-ratio cycle problem really is all about distances. As a result, we obtain a faster primal maxflow and min-cost flow solver that also extends to incremental graphs.

Tuesday, September 22 2026, 00:00

Smoothed Analysis of Inconsistent A*

Authors: Zhiyang Chen, Hailong Yao

The A* search is a fundamental path-finding algorithm in artificial intelligence. While admissible and consistent heuristics guarantee efficient performance by expanding each state at most once, modern search applications frequently employ powerful but inconsistent heuristics derived from machine learning, randomized evaluations, etc. A long-standing theoretical barrier to using these inconsistent heuristics is the risk of catastrophic node re-expansion, which yields a worst-case exponential time complexity of $Ω(2^n)$. However, empirical observations contradict this pessimistic bound, demonstrating that inconsistent A* operates highly efficiently in practice. To bridge this significant gap between theory and practice, this paper presents the first smoothed analysis of the A* algorithm using inconsistent heuristics. We model typical real-world noise by applying slight random perturbations to the edge weights of worst-case search graphs. Our main result proves that the expected smoothed time complexity of inconsistent A* is bounded by a polynomial, specifically a total iteration number of $O(n^2 m κ)$, where $n$ is the number of nodes, $m$ is the number of edges, and $κ$ controls the scale of random perturbations. Furthermore, we also show that this result naturally extends to the functionally equivalent problem of Dijkstra's algorithm on negative-weight graphs.

Authors: Zhiyang Chen, Hailong Yao

The A* search is a fundamental path-finding algorithm in artificial intelligence. While admissible and consistent heuristics guarantee efficient performance by expanding each state at most once, modern search applications frequently employ powerful but inconsistent heuristics derived from machine learning, randomized evaluations, etc. A long-standing theoretical barrier to using these inconsistent heuristics is the risk of catastrophic node re-expansion, which yields a worst-case exponential time complexity of $Ω(2^n)$. However, empirical observations contradict this pessimistic bound, demonstrating that inconsistent A* operates highly efficiently in practice. To bridge this significant gap between theory and practice, this paper presents the first smoothed analysis of the A* algorithm using inconsistent heuristics. We model typical real-world noise by applying slight random perturbations to the edge weights of worst-case search graphs. Our main result proves that the expected smoothed time complexity of inconsistent A* is bounded by a polynomial, specifically a total iteration number of $O(n^2 m κ)$, where $n$ is the number of nodes, $m$ is the number of edges, and $κ$ controls the scale of random perturbations. Furthermore, we also show that this result naturally extends to the functionally equivalent problem of Dijkstra's algorithm on negative-weight graphs.

Tuesday, September 22 2026, 00:00

A general counting and sampling Lovász local lemma

Authors: Vishesh Jain, Clayton Mizgerd, Huy Tuan Pham

Consider a constraint satisfaction problem $\mathbf{C}$ on finitely many independent random variables with dependency graph $G$. Let $p_a$ be the violation probability of a constraint $a\in \mathbf{C}$ and $N_G^2 (a)$ the set of constraints at distance one or two from $a$ in $G$. Suppose that, there exists $x\in (0,1)^{\mathbf{C}}$ such that, for a sufficiently small universal constant $c > 0$, and for all $a \in \mathbf{C}$, \[ p_a \leq c \cdot x_a \prod_{b\in N_G^2(a)}(1-x_b). \] Under the above analog of the asymmetric Lovász Local Lemma, we give an FPRAS for the probability that all constraints are satisfied, and an approximate sampler, running in polynomial expected time, for the product distribution conditioned on this event. The degree of the polynomial in the running time is independent of the domain sizes, constraint sizes, or degree of the dependency graph. Up to the choice of the constant $c$, our condition on $p_a$ matches known hardness results. Our work builds on the method of Liu, Wang, Yin, Zhang, and Zhou, who obtained an FPRAS for the probability of satisfaction in the setting of the symmetric Lovász Local Lemma. Our sampling result is new even in this special case.

Authors: Vishesh Jain, Clayton Mizgerd, Huy Tuan Pham

Consider a constraint satisfaction problem $\mathbf{C}$ on finitely many independent random variables with dependency graph $G$. Let $p_a$ be the violation probability of a constraint $a\in \mathbf{C}$ and $N_G^2 (a)$ the set of constraints at distance one or two from $a$ in $G$. Suppose that, there exists $x\in (0,1)^{\mathbf{C}}$ such that, for a sufficiently small universal constant $c > 0$, and for all $a \in \mathbf{C}$, \[ p_a \leq c \cdot x_a \prod_{b\in N_G^2(a)}(1-x_b). \] Under the above analog of the asymmetric Lovász Local Lemma, we give an FPRAS for the probability that all constraints are satisfied, and an approximate sampler, running in polynomial expected time, for the product distribution conditioned on this event. The degree of the polynomial in the running time is independent of the domain sizes, constraint sizes, or degree of the dependency graph. Up to the choice of the constant $c$, our condition on $p_a$ matches known hardness results. Our work builds on the method of Liu, Wang, Yin, Zhang, and Zhou, who obtained an FPRAS for the probability of satisfaction in the setting of the symmetric Lovász Local Lemma. Our sampling result is new even in this special case.

Tuesday, September 22 2026, 00:00

A Polynomial Kernel for Planar Directed Feedback Vertex Set

Authors: Zimo Sheng, Mingyu Xiao

The Directed Feedback Vertex Set problem (DFVS) asks whether a digraph can be made acyclic by deleting at most $k$ vertices. Whether DFVS admits a polynomial kernel parameterized by $k$ is a major open problem in kernelization, even for planar digraphs. We resolve the planar case by giving a deterministic kernel with $O(k^{66}\log^2 k)$ vertices and arcs. Our algorithm proceeds in three stages. First, we apply structural reduction rules to the input digraph, bounding the number of directed faces and some special vertices. Second, we pass to the planar dual, where vertex deletion corresponds to adding groups of reverse arcs to make each weakly connected component strongly connected. The structural bounds in the first stage yield a small retained vertex set in the dual. We then compress the dual instance by identifying vertices with the same distance records from this retained vertex set. The main technical contribution is a directed-cut argument showing that this identification preserves feasibility. Finally, we transform the polynomial-size dual instance back into an instance of Planar Directed Feedback Vertex Set via a $3$-CNF encoding and a planar graph construction.

Authors: Zimo Sheng, Mingyu Xiao

The Directed Feedback Vertex Set problem (DFVS) asks whether a digraph can be made acyclic by deleting at most $k$ vertices. Whether DFVS admits a polynomial kernel parameterized by $k$ is a major open problem in kernelization, even for planar digraphs. We resolve the planar case by giving a deterministic kernel with $O(k^{66}\log^2 k)$ vertices and arcs. Our algorithm proceeds in three stages. First, we apply structural reduction rules to the input digraph, bounding the number of directed faces and some special vertices. Second, we pass to the planar dual, where vertex deletion corresponds to adding groups of reverse arcs to make each weakly connected component strongly connected. The structural bounds in the first stage yield a small retained vertex set in the dual. We then compress the dual instance by identifying vertices with the same distance records from this retained vertex set. The main technical contribution is a directed-cut argument showing that this identification preserves feasibility. Finally, we transform the polynomial-size dual instance back into an instance of Planar Directed Feedback Vertex Set via a $3$-CNF encoding and a planar graph construction.

Tuesday, September 22 2026, 00:00

Budget-Independent Influence Maximization in Nearly Linear Time