Theory of Computing Report

Authors: Jincheng Guan, Shuai Shao, Zhuxiao Tang

We study Boolean Holant problems with complex-valued signature sets closed under conjugation. Such sets arise naturally in tensor-network expressions for classical strong simulation of quantum circuits. We prove a complexity dichotomy for such problems with an explicit tractability criterion. This extends the dichotomy for real-valued Holant problems, with the same four tractability conditions. Our proofs use Xia's projective binary group framework and quantum entanglement theory. The conjugate closure assumption precisely makes $k$-uniformity, directly applicable to the classification of Holant problems, by realizing reduced density matrices via Holant gadgets. We also use the classification of absolutely maximally entangled states to resolve a particular $6$-ary obstruction in our inductive proof of the \#P-hardness.

Authors: Jincheng Guan, Shuai Shao, Zhuxiao Tang

We study Boolean Holant problems with complex-valued signature sets closed under conjugation. Such sets arise naturally in tensor-network expressions for classical strong simulation of quantum circuits. We prove a complexity dichotomy for such problems with an explicit tractability criterion. This extends the dichotomy for real-valued Holant problems, with the same four tractability conditions. Our proofs use Xia's projective binary group framework and quantum entanglement theory. The conjugate closure assumption precisely makes $k$-uniformity, directly applicable to the classification of Holant problems, by realizing reduced density matrices via Holant gadgets. We also use the classification of absolutely maximally entangled states to resolve a particular $6$-ary obstruction in our inductive proof of the \#P-hardness.

Monday, September 14 2026, 00:00

QMA has perfect completeness

Authors: Sabee Grewal, Dorian Rudolph

We prove $\mathsf{QMA} = \mathsf{QMA_1}$, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and $X$ gates, yielding a universal gate set for $\mathsf{QMA_1}$. As a consequence, quantum $3$-SAT is $\mathsf{QMA}$-complete. The construction relativizes to classical oracles, so known classical-oracle separations of $\mathsf{QMA}$ from $\mathsf{QCMA}$ extend to $\mathsf{QMA_1}$.

Authors: Sabee Grewal, Dorian Rudolph

We prove $\mathsf{QMA} = \mathsf{QMA_1}$, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and $X$ gates, yielding a universal gate set for $\mathsf{QMA_1}$. As a consequence, quantum $3$-SAT is $\mathsf{QMA}$-complete. The construction relativizes to classical oracles, so known classical-oracle separations of $\mathsf{QMA}$ from $\mathsf{QCMA}$ extend to $\mathsf{QMA_1}$.

Monday, September 14 2026, 00:00

Average-case hardness of Betti number estimation

Authors: Sergii Strelchuk, Sathyawageeswar Subramanian, Adam Wesołowski

We establish the average-case hardness of Betti number estimation on random clique complexes via a reduction from the planted clique problem. We further show that our reduction implies a series of hardness results for many problems in both classical and quantum Topological Data Analysis (qTDA). Under the classical planted clique conjecture, no randomized polynomial-time Betti number estimator achieves additive error below $\tfrac12$ with constant advantage. Under a new quantum planted clique conjecture that we introduce, the same conclusion holds for quantum polynomial-time algorithms. We also obtain related conditional hardness results for homology vanishing, additive approximations with larger error tolerances, preparation of simplex and harmonic states, cycle recovery, and counting eigenvalues at low energy. Our reduction clarifies the structural requirements for quantum advantage in TDA and provides a new lens to investigate the classical and quantum complexity of related problems.

Authors: Sergii Strelchuk, Sathyawageeswar Subramanian, Adam Wesołowski

We establish the average-case hardness of Betti number estimation on random clique complexes via a reduction from the planted clique problem. We further show that our reduction implies a series of hardness results for many problems in both classical and quantum Topological Data Analysis (qTDA). Under the classical planted clique conjecture, no randomized polynomial-time Betti number estimator achieves additive error below $\tfrac12$ with constant advantage. Under a new quantum planted clique conjecture that we introduce, the same conclusion holds for quantum polynomial-time algorithms. We also obtain related conditional hardness results for homology vanishing, additive approximations with larger error tolerances, preparation of simplex and harmonic states, cycle recovery, and counting eigenvalues at low energy. Our reduction clarifies the structural requirements for quantum advantage in TDA and provides a new lens to investigate the classical and quantum complexity of related problems.

Monday, September 14 2026, 00:00

Deterministic NC Quadratic Root Counting in Characteristic Two

Authors: Sanyam Agarwal, Gorav Jindal

Counting satisfying assignments of Boolean formulas is a basic problem in theoretical computer science, with $\#3\text{-}\SAT$ as the standard $\SharpP$-complete problem. More generally, counting the solutions of a system of polynomial equations over $\F_2$ is $\SharpP$-complete. Here we focus on the more structured problem of counting the solutions of a single polynomial equation. For polynomial equations over finite fields, Ehrenfeucht and Karpinski \cite{computationalcomplexityofxorandcountingproblems1990} showed a sharp difference between degrees two and three: quadratic root counting is solvable in polynomial time, while the degree-three problem is $\SharpP$-complete. Their quadratic algorithm is sequential. For fixed finite fields, Ishai et al.~\cite{ishai2012randomizing} later gave deterministic parallel algorithms in odd characteristic and randomized parallel algorithms in characteristic two. We give a deterministic $\NC$ algorithm for exactly counting the solutions of a quadratic polynomial equation over every fixed finite field of characteristic two. Our algorithm separates the radical and uses the absolute trace to realize the bit distinguishing the two nondegenerate finite-field types as the Arf invariant \cite{arf1941untersuchungen} of a quadratic form over $\F_2$. It then recovers that invariant from an integral matrix using Browder's determinant criterion \cite{browder2006complete}. This replaces the randomized canonical-form step in the algorithm of Ishai et al.

Authors: Sanyam Agarwal, Gorav Jindal

Counting satisfying assignments of Boolean formulas is a basic problem in theoretical computer science, with $\#3\text{-}\SAT$ as the standard $\SharpP$-complete problem. More generally, counting the solutions of a system of polynomial equations over $\F_2$ is $\SharpP$-complete. Here we focus on the more structured problem of counting the solutions of a single polynomial equation. For polynomial equations over finite fields, Ehrenfeucht and Karpinski \cite{computationalcomplexityofxorandcountingproblems1990} showed a sharp difference between degrees two and three: quadratic root counting is solvable in polynomial time, while the degree-three problem is $\SharpP$-complete. Their quadratic algorithm is sequential. For fixed finite fields, Ishai et al.~\cite{ishai2012randomizing} later gave deterministic parallel algorithms in odd characteristic and randomized parallel algorithms in characteristic two. We give a deterministic $\NC$ algorithm for exactly counting the solutions of a quadratic polynomial equation over every fixed finite field of characteristic two. Our algorithm separates the radical and uses the absolute trace to realize the bit distinguishing the two nondegenerate finite-field types as the Arf invariant \cite{arf1941untersuchungen} of a quadratic form over $\F_2$. It then recovers that invariant from an integral matrix using Browder's determinant criterion \cite{browder2006complete}. This replaces the randomized canonical-form step in the algorithm of Ishai et al.

Monday, September 14 2026, 00:00

The Low-Individual-Degree Test Without the Diagonal-Lines Test Is Not Quantum-Sound

Authors: Tianrun Zhao

To prove the quantum soundness of the classical low-individual-degree test, the authors of \cite{JNVWY20LID} defined three subtests, namely the axis-parallel lines test, the self-consistency test, and the diagonal-lines test. An interesting question is whether the diagonal-lines test can be removed. In this paper, we show that the diagonal-lines test cannot simply be removed without another compatibility mechanism. Consequently, replacing the "conditional linear functions" by "coordinate deletion functions" in the proof of MIP*=RE, as mentioned in \cite{JNVWY20LID}, does not by itself preserve the required soundness. The authors of \cite{JNVWY20LID} found an example that requires the diagonal-lines test when $(m, d, q) = (2, 2, 4)$; we give an example when $(m, d) = (2, 2)$ and $q$ is any odd prime.

Authors: Tianrun Zhao

To prove the quantum soundness of the classical low-individual-degree test, the authors of \cite{JNVWY20LID} defined three subtests, namely the axis-parallel lines test, the self-consistency test, and the diagonal-lines test. An interesting question is whether the diagonal-lines test can be removed. In this paper, we show that the diagonal-lines test cannot simply be removed without another compatibility mechanism. Consequently, replacing the "conditional linear functions" by "coordinate deletion functions" in the proof of MIP*=RE, as mentioned in \cite{JNVWY20LID}, does not by itself preserve the required soundness. The authors of \cite{JNVWY20LID} found an example that requires the diagonal-lines test when $(m, d, q) = (2, 2, 4)$; we give an example when $(m, d) = (2, 2)$ and $q$ is any odd prime.

Monday, September 14 2026, 00:00

The Information Complexity of Decision Trees

Authors: Avantika Agarwal, Shalev Ben-David, Eric Blais

We define and study a measure of information complexity for randomized decision trees. We prove three main results about this complexity measure: Information equals amortized size complexity. We show that the information complexity of randomized decision tree is equal to the logarithm of the amortized worst-case randomized tree size complexity of computing a function f. That is, when computing f on n inputs, the logarithm of the randomized tree size is exactly equal to the amount of information needed to compute the function. Information allows for tree size compression. We show that even when computing f on a single input, the information complexity can be used to compress the size of a tree, if we allow a small loss in success probability. With the recent characterization of Chattopadhyay, Dahiya, Mande, Radhakrishnan, and Sanyal (2023), this result shows that the depth of AND-OR trees can also be compressed in terms of information complexity. Direct Product Theorems. We show that the success-conditioned variant of information complexity satisfies a perfect direct product theorem. This result gives an information complexity analogue of the direct product theorem for success-conditioned randomized query complexity by Ben-David and Blais (2025).

Authors: Avantika Agarwal, Shalev Ben-David, Eric Blais

We define and study a measure of information complexity for randomized decision trees. We prove three main results about this complexity measure: Information equals amortized size complexity. We show that the information complexity of randomized decision tree is equal to the logarithm of the amortized worst-case randomized tree size complexity of computing a function f. That is, when computing f on n inputs, the logarithm of the randomized tree size is exactly equal to the amount of information needed to compute the function. Information allows for tree size compression. We show that even when computing f on a single input, the information complexity can be used to compress the size of a tree, if we allow a small loss in success probability. With the recent characterization of Chattopadhyay, Dahiya, Mande, Radhakrishnan, and Sanyal (2023), this result shows that the depth of AND-OR trees can also be compressed in terms of information complexity. Direct Product Theorems. We show that the success-conditioned variant of information complexity satisfies a perfect direct product theorem. This result gives an information complexity analogue of the direct product theorem for success-conditioned randomized query complexity by Ben-David and Blais (2025).

Monday, September 14 2026, 00:00

Almost Empty Monochromatic Triangles With Many Colors

Authors: Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen

Given integers $c\geq 2$ and $s\geq 0$, let $\mathsf{M}_3(c,s)$ denote the least integer such that every set of at least $\mathsf{M}_3(c,s)$ points in the plane, no three on a line, colored with $c$ colors, contains a monochromatic triangle with at most $s$ interior points. Further, let $λ_3(c)$ be the least integer such that $\mathsf{M}_3(c,λ_3(c))<\infty$. \citet{colorempty} proved that, for every $c\geq 2$, $$\left\lfloor\frac{c-1}{2}\right\rfloor \leq λ_3(c)\leq c-2.$$ Later, \citet{cravioto2019almost} improved the upper bound to $c-3$, for $c\geq 4$. In this paper, we refine their argument to obtain the following asymptotic improvement: $$λ_3(c) \leq c-\sqrt{c\log c}+o (\sqrt{c\log c} ),$$ for all sufficiently large $c$. We also show that every $c$-coloring of a sufficiently large Horton set contains a monochromatic triangle with at most $\lfloor \frac{c-1}{2} \rfloor$ interior points. This shows that the aforementioned lower bound on $λ_3(c)$ is sharp within the class of Horton sets. We conclude with a conjecture on the large-color asymptotics of $λ_3(c)$.

Authors: Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen

Given integers $c\geq 2$ and $s\geq 0$, let $\mathsf{M}_3(c,s)$ denote the least integer such that every set of at least $\mathsf{M}_3(c,s)$ points in the plane, no three on a line, colored with $c$ colors, contains a monochromatic triangle with at most $s$ interior points. Further, let $λ_3(c)$ be the least integer such that $\mathsf{M}_3(c,λ_3(c))<\infty$. \citet{colorempty} proved that, for every $c\geq 2$, $$\left\lfloor\frac{c-1}{2}\right\rfloor \leq λ_3(c)\leq c-2.$$ Later, \citet{cravioto2019almost} improved the upper bound to $c-3$, for $c\geq 4$. In this paper, we refine their argument to obtain the following asymptotic improvement: $$λ_3(c) \leq c-\sqrt{c\log c}+o (\sqrt{c\log c} ),$$ for all sufficiently large $c$. We also show that every $c$-coloring of a sufficiently large Horton set contains a monochromatic triangle with at most $\lfloor \frac{c-1}{2} \rfloor$ interior points. This shows that the aforementioned lower bound on $λ_3(c)$ is sharp within the class of Horton sets. We conclude with a conjecture on the large-color asymptotics of $λ_3(c)$.

Monday, September 14 2026, 00:00

Direct Topology Tracking in Continuous Implicit Models

Authors: Guanqun Ma, David Lenz, Kaiyuan Tang, Hanqi Guo, Chaoli Wang, Tom Peterka, Bei Wang

We present a framework for tracking topological features directly within continuous implicit models. Such models, including implicit neural representations (INRs) and multivariate functional approximations (MFAs), are increasingly adopted to represent scientific data without the resolution constraints of discrete grids. They offer compact, smooth, and differentiable representations of complex fields, enabling new opportunities for high-performance data storage, reconstruction, and analysis. Given a continuous implicit model, our method tracks the evolution of critical points by querying the model and its derivatives, thereby eliminating the need to resample onto a grid. This approach enables faithful feature tracking while avoiding discretization-induced artifacts such as aliasing. We demonstrate the generality of our framework across a range of implicit representations, including analytic functions, MFAs, and INRs, and show that it produces smooth, coherent critical point trajectories. By enabling feature tracking directly on continuous representations, our method supports a new class of feature-driven visualization workflows centered on implicit models.

Authors: Guanqun Ma, David Lenz, Kaiyuan Tang, Hanqi Guo, Chaoli Wang, Tom Peterka, Bei Wang

We present a framework for tracking topological features directly within continuous implicit models. Such models, including implicit neural representations (INRs) and multivariate functional approximations (MFAs), are increasingly adopted to represent scientific data without the resolution constraints of discrete grids. They offer compact, smooth, and differentiable representations of complex fields, enabling new opportunities for high-performance data storage, reconstruction, and analysis. Given a continuous implicit model, our method tracks the evolution of critical points by querying the model and its derivatives, thereby eliminating the need to resample onto a grid. This approach enables faithful feature tracking while avoiding discretization-induced artifacts such as aliasing. We demonstrate the generality of our framework across a range of implicit representations, including analytic functions, MFAs, and INRs, and show that it produces smooth, coherent critical point trajectories. By enabling feature tracking directly on continuous representations, our method supports a new class of feature-driven visualization workflows centered on implicit models.

Monday, September 14 2026, 00:00

Learning Sparse Quantum States

Authors: Aniruddha Sen

We study the problem of tomography for $k$-sparse quantum states. In contrast to classical distribution learning, where tight sample and time complexity bounds in terms of support size are well understood, no non-trivial bounds were previously shown for this problem. We give the first near optimal algorithm for learning $n$-qubit $k$-sparse pure quantum states, obtaining fidelity at least $1-\varepsilon$ with high probability using $\tilde{O}(k/\varepsilon)$ copies of the state and $\tilde{O}(kn/\varepsilon)$ time. Both bounds are optimal up to polylogarithmic factors. As an implication, we also obtain an algorithm with near optimal $\tilde{O}(kr/\varepsilon)$ sample complexity for learning $k$-sparse rank-$r$ mixed states, via the random purification channel technique. Obtaining time complexity nearly matching the sample complexity, for $r>1$, remains an important open question.

Authors: Aniruddha Sen

We study the problem of tomography for $k$-sparse quantum states. In contrast to classical distribution learning, where tight sample and time complexity bounds in terms of support size are well understood, no non-trivial bounds were previously shown for this problem. We give the first near optimal algorithm for learning $n$-qubit $k$-sparse pure quantum states, obtaining fidelity at least $1-\varepsilon$ with high probability using $\tilde{O}(k/\varepsilon)$ copies of the state and $\tilde{O}(kn/\varepsilon)$ time. Both bounds are optimal up to polylogarithmic factors. As an implication, we also obtain an algorithm with near optimal $\tilde{O}(kr/\varepsilon)$ sample complexity for learning $k$-sparse rank-$r$ mixed states, via the random purification channel technique. Obtaining time complexity nearly matching the sample complexity, for $r>1$, remains an important open question.

Monday, September 14 2026, 00:00

Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to $β\leq \frac{1}{2}+\varepsilon$

Authors: Mathews Boban, Anqi Li, Shayan Oveis Gharan

We introduce a new family of trickledown theorems, a.k.a., local to global technique to bound the spectral gap of the Glauber dynamics for multi-state spin systems. In this technique instead of upper-bounding the influence matrix of a link of co-dimension 2 by $λI$ (where $λ$ is the second eigenvalue of the link), we upper-bound the influence matrix after a carefully chosen rank-1 shift. The rank-1 shift allows for a significantly smaller upper-bound but it comes at the cost of bounding the average loss due to rank-1 perturbations. As an application we use this method to show that the natural Glauber dynamics mixes in polynomial time to generate samples from the Sherrington-Kirkpatrick model for $β\leq \tfrac{1}{2}+\varepsilon$, for an absolute constant $\varepsilon>0$. At the heart of the proof we manage to bound the loss due to rank-1 perturbations by averaging over all links of co-dimension 2.

Authors: Mathews Boban, Anqi Li, Shayan Oveis Gharan

We introduce a new family of trickledown theorems, a.k.a., local to global technique to bound the spectral gap of the Glauber dynamics for multi-state spin systems. In this technique instead of upper-bounding the influence matrix of a link of co-dimension 2 by $λI$ (where $λ$ is the second eigenvalue of the link), we upper-bound the influence matrix after a carefully chosen rank-1 shift. The rank-1 shift allows for a significantly smaller upper-bound but it comes at the cost of bounding the average loss due to rank-1 perturbations. As an application we use this method to show that the natural Glauber dynamics mixes in polynomial time to generate samples from the Sherrington-Kirkpatrick model for $β\leq \tfrac{1}{2}+\varepsilon$, for an absolute constant $\varepsilon>0$. At the heart of the proof we manage to bound the loss due to rank-1 perturbations by averaging over all links of co-dimension 2.

Monday, September 14 2026, 00:00

Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds

Authors: Pritish Kamath, Ravi Kumar, Pasin Manurangsi

We study combinatorial optimization problems under the constraint of $ε$-differential privacy ($ε$-DP). Given the strong lower bounds for explicitly outputting solutions, we work within the implicit representation framework of Gupta et al. (SODA 2010), where a private polynomial-time randomized "encoder" generates a representation of a solution, and a "decoder" uses this representation along with the input to extract a valid final solution. In this work, we generalize this framework by allowing the encoder to run in fixed-parameter tractable time. This circumvents approximation barriers inherent to polynomial-time algorithms and obtains improved guarantees for many fundamental combinatorial optimization problems. Finally, we establish the first representation-independent lower bounds for our framework. Assuming a non-uniform variant of the Gap Exponential Time Hypothesis, for sufficiently small $ε> 0$, we prove that no $ε$-DP encoder-decoder pair can achieve certain approximation guarantees, if the decoder runs in subexponential time. We further provide representation-dependent lower bounds that hold even for larger $ε$.

Authors: Pritish Kamath, Ravi Kumar, Pasin Manurangsi

We study combinatorial optimization problems under the constraint of $ε$-differential privacy ($ε$-DP). Given the strong lower bounds for explicitly outputting solutions, we work within the implicit representation framework of Gupta et al. (SODA 2010), where a private polynomial-time randomized "encoder" generates a representation of a solution, and a "decoder" uses this representation along with the input to extract a valid final solution. In this work, we generalize this framework by allowing the encoder to run in fixed-parameter tractable time. This circumvents approximation barriers inherent to polynomial-time algorithms and obtains improved guarantees for many fundamental combinatorial optimization problems. Finally, we establish the first representation-independent lower bounds for our framework. Assuming a non-uniform variant of the Gap Exponential Time Hypothesis, for sufficiently small $ε> 0$, we prove that no $ε$-DP encoder-decoder pair can achieve certain approximation guarantees, if the decoder runs in subexponential time. We further provide representation-dependent lower bounds that hold even for larger $ε$.

Monday, September 14 2026, 00:00

Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs

Authors: Zhidan Li, Kuan Yang

We develop a framework for deterministic approximate counting of multi-spin systems beyond bounded-degree graphs. The algorithm recursively constructs rational polytopes containing the true marginal vectors and uses linear-fractional programming to obtain certified bounds on marginal ratios. For positive interactions on graphs of polynomial connective constant $D$, we establish strong spatial mixing and a fully polynomial-time approximation scheme (\textbf{FPTAS}) whenever $Dc<1$, where $c$ bounds the Birkhoff contraction coefficients of the interactions. We further extend the framework to proper colorings of sparse Erdős-Rényi random graphs using recursion on permissive blocks. For every fixed $η\in(0,1)$, sufficiently large fixed $d$, and fixed integer $q\ge(2+η)d$, we obtain an \textbf{FPTAS} for counting proper $q$-colorings of $G\sim\mathcal G(n,d/n)$ with high probability over $G$. This improves the leading constant $3$ in the earlier counting guarantee of Yin and Zhang (APPROX/RANDOM, 2016) to $2$, and asymptotically matches the spatial mixing regime established by Yin (ICALP, 2014).

Authors: Zhidan Li, Kuan Yang

We develop a framework for deterministic approximate counting of multi-spin systems beyond bounded-degree graphs. The algorithm recursively constructs rational polytopes containing the true marginal vectors and uses linear-fractional programming to obtain certified bounds on marginal ratios. For positive interactions on graphs of polynomial connective constant $D$, we establish strong spatial mixing and a fully polynomial-time approximation scheme (\textbf{FPTAS}) whenever $Dc<1$, where $c$ bounds the Birkhoff contraction coefficients of the interactions. We further extend the framework to proper colorings of sparse Erdős-Rényi random graphs using recursion on permissive blocks. For every fixed $η\in(0,1)$, sufficiently large fixed $d$, and fixed integer $q\ge(2+η)d$, we obtain an \textbf{FPTAS} for counting proper $q$-colorings of $G\sim\mathcal G(n,d/n)$ with high probability over $G$. This improves the leading constant $3$ in the earlier counting guarantee of Yin and Zhang (APPROX/RANDOM, 2016) to $2$, and asymptotically matches the spatial mixing regime established by Yin (ICALP, 2014).

Monday, September 14 2026, 00:00

Exponential Lower Bounds for Integer-Weighted Shortest-Paths Preservers of DAGs

Authors: Michael Yi Wang, Nicole Wein

We study a graph simplification problem introduced by Bernstein, Bodwin, and Wein [ITCS'24]. We start with a graph with arbitrarily large positive edge weights and the goal is to reweight the edges to small aspect ratio (ratio between largest and smallest weight) while preserving the shortest paths structure (the sequence of vertices and edges along shortest paths). They studied whether polynomial aspect ratio is always possible. They proved that for general graphs, both directed and undirected, it is not: there exist graphs for which any shortest-paths preserving reweighting requires exponential aspect ratio. In contrast, they showed that every DAG (directed acyclic graph) admits a reweighting with linear aspect ratio. However, the resulting edge weights are not integers. This motivated them to pose the open question of whether all DAGs admit a reweighting with polynomially-bounded integer edge weights. Our main result is to answer this question in the negative: we prove that there exist DAGs for which any shortest-paths preserving integer reweighting requires weights of size $2^{Ω(n)}$. In fact, this is even true when the DAG has very simple structure: 3 layers of vertices with only 3 vertices in the middle layer. In contrast, we show that if the number of vertices in the middle layer is decreased to 2, then a linear upper bound is possible. We extend our exponential lower bound to the approximate version of the problem where only a single $α$-approximate shortest path in the original graph must be preserved as an exact shortest path in the reweighted graph. Our exponential lower bound holds even for any finite approximation ratio $α>1$.

Authors: Michael Yi Wang, Nicole Wein

We study a graph simplification problem introduced by Bernstein, Bodwin, and Wein [ITCS'24]. We start with a graph with arbitrarily large positive edge weights and the goal is to reweight the edges to small aspect ratio (ratio between largest and smallest weight) while preserving the shortest paths structure (the sequence of vertices and edges along shortest paths). They studied whether polynomial aspect ratio is always possible. They proved that for general graphs, both directed and undirected, it is not: there exist graphs for which any shortest-paths preserving reweighting requires exponential aspect ratio. In contrast, they showed that every DAG (directed acyclic graph) admits a reweighting with linear aspect ratio. However, the resulting edge weights are not integers. This motivated them to pose the open question of whether all DAGs admit a reweighting with polynomially-bounded integer edge weights. Our main result is to answer this question in the negative: we prove that there exist DAGs for which any shortest-paths preserving integer reweighting requires weights of size $2^{Ω(n)}$. In fact, this is even true when the DAG has very simple structure: 3 layers of vertices with only 3 vertices in the middle layer. In contrast, we show that if the number of vertices in the middle layer is decreased to 2, then a linear upper bound is possible. We extend our exponential lower bound to the approximate version of the problem where only a single $α$-approximate shortest path in the original graph must be preserved as an exact shortest path in the reweighted graph. Our exponential lower bound holds even for any finite approximation ratio $α>1$.

Monday, September 14 2026, 00:00

A Tight $\widetilde Ω(\sqrt{m})$ Information-Theoretic Lower Bound for Randomized Online Set Cover

Authors: Ilan Doron-Arad, Joseph, Naor

Online set cover is a fundamental problem in online algorithms, admitting a deterministic $O(\log m\log n)$-competitive algorithm, where $m$ is the number of sets and $n$ is the number of elements. This is essentially tight for deterministic algorithms as well as for polynomial-time randomized algorithms assuming $\mathrm{NP}\not\subseteq\mathrm{BPP}$. However, the best lower bound known for information-theoretic (computationally unlimited) randomized algorithms against an oblivious adversary is only $Ω(\log m)$, whereas the upper bound in terms of $m$ is $O(\sqrt m\log m)=\widetilde O(\sqrt m)$. We prove an $Ω(\sqrt m)$ lower bound for information-theoretic randomized unweighted online set cover, showing that even with unbounded computational power, randomization cannot achieve an $O(\log m)$-competitive ratio. Specifically, our lower bound rules out $O(\log m\cdot\log^{1/2-\varepsilon} n)$-competitive algorithms for every constant $\varepsilon>0$. Our techniques also prove an $Ω(m^{1/3})$ lower bound in the random-order model, and show that every algorithm with $poly(m)$ memory has competitive ratio $Ω(m/\log m)$, even with unlimited computation between requests.

Authors: Ilan Doron-Arad, Joseph, Naor

Online set cover is a fundamental problem in online algorithms, admitting a deterministic $O(\log m\log n)$-competitive algorithm, where $m$ is the number of sets and $n$ is the number of elements. This is essentially tight for deterministic algorithms as well as for polynomial-time randomized algorithms assuming $\mathrm{NP}\not\subseteq\mathrm{BPP}$. However, the best lower bound known for information-theoretic (computationally unlimited) randomized algorithms against an oblivious adversary is only $Ω(\log m)$, whereas the upper bound in terms of $m$ is $O(\sqrt m\log m)=\widetilde O(\sqrt m)$. We prove an $Ω(\sqrt m)$ lower bound for information-theoretic randomized unweighted online set cover, showing that even with unbounded computational power, randomization cannot achieve an $O(\log m)$-competitive ratio. Specifically, our lower bound rules out $O(\log m\cdot\log^{1/2-\varepsilon} n)$-competitive algorithms for every constant $\varepsilon>0$. Our techniques also prove an $Ω(m^{1/3})$ lower bound in the random-order model, and show that every algorithm with $poly(m)$ memory has competitive ratio $Ω(m/\log m)$, even with unlimited computation between requests.

Monday, September 14 2026, 00:00

Motifs in temporal hypergraphs

Authors: Quintino Francesco Lotito, Lorenzo Betti, Federico Battiston, Giuseppe Francesco Italiano

Network motifs, recurrent local patterns of interactions in graphs, provide fundamental insights on the interplay between structure and functionality in complex systems. Many real-world systems are not well represented by traditional static pairwise networks, as interactions may involve groups of nodes, occur over time, or encode directionality. In this paper, we introduce temporal motifs for hypergraphs and directed hypergraphs, extending motif analysis to timestamped many-body interactions. We formalize the corresponding mining problem, study the combinatorial structure of these motifs, and develop exact algorithms for their enumeration. In particular, we propose a dynamic programming algorithm that substantially reduces the computational cost of motif mining, achieving orders of magnitude speedups on empirical datasets. We also introduce a null model for temporal hypergraphs to assess the statistical over- and under-expression of motifs. Applying the proposed framework to real-world datasets from different domains, including face-to-face contacts, scientific collaborations, e-mail exchanges, and Bitcoin transactions, we show that temporal hypergraph motifs reveal distinct forms of local organization across systems. Finally, we demonstrate their use as an exploratory tool through focused case studies on persistent patterns in scientific collaborations and e-mail communications.

Authors: Quintino Francesco Lotito, Lorenzo Betti, Federico Battiston, Giuseppe Francesco Italiano

Network motifs, recurrent local patterns of interactions in graphs, provide fundamental insights on the interplay between structure and functionality in complex systems. Many real-world systems are not well represented by traditional static pairwise networks, as interactions may involve groups of nodes, occur over time, or encode directionality. In this paper, we introduce temporal motifs for hypergraphs and directed hypergraphs, extending motif analysis to timestamped many-body interactions. We formalize the corresponding mining problem, study the combinatorial structure of these motifs, and develop exact algorithms for their enumeration. In particular, we propose a dynamic programming algorithm that substantially reduces the computational cost of motif mining, achieving orders of magnitude speedups on empirical datasets. We also introduce a null model for temporal hypergraphs to assess the statistical over- and under-expression of motifs. Applying the proposed framework to real-world datasets from different domains, including face-to-face contacts, scientific collaborations, e-mail exchanges, and Bitcoin transactions, we show that temporal hypergraph motifs reveal distinct forms of local organization across systems. Finally, we demonstrate their use as an exploratory tool through focused case studies on persistent patterns in scientific collaborations and e-mail communications.

Monday, September 14 2026, 00:00

A Non-constant Lower Bound for Grammar-Based Compression with Greedy

Authors: Danny Hucke

We prove a lower bound of Ω(log n/ log log n) on the approximation ratio of the global grammar-based compression algorithm Greedy. To our knowledge, the previously best lower bound was a constant, and the existence of a nonconstant lower bound had remained open for more than twenty years. Our bound holds on an infinite family of words of length n, over alphabets of growing size, for every execution using left-to-right occurrence replacement and arbitrary tie-breaking. The lower bound is also formally verified in Lean 4.

Authors: Danny Hucke

We prove a lower bound of Ω(log n/ log log n) on the approximation ratio of the global grammar-based compression algorithm Greedy. To our knowledge, the previously best lower bound was a constant, and the existence of a nonconstant lower bound had remained open for more than twenty years. Our bound holds on an infinite family of words of length n, over alphabets of growing size, for every execution using left-to-right occurrence replacement and arbitrary tie-breaking. The lower bound is also formally verified in Lean 4.

Monday, September 14 2026, 00:00

Accelerating the Local Push Primitive for PageRank Computation

Authors: Guanyu Cui, Zhewei Wei, Mingji Yang

We propose a local algorithm that computes an $\varepsilon$-approximate PageRank vector in the sense of Andersen, Chung, and Lang (ACL; Internet Math. 2007) with teleportation parameter $α$ in $\widetilde{O}\bigl(1 / \bigl(\sqrtα \, \varepsilon\bigr)\bigr)$ time with high probability, improving the $O\bigl(1/(α\varepsilon)\bigr)$ running time of their original local push method. Our method also applies to the $\ell_1$-regularized PageRank problem with a running time of $\widetilde{O}\bigl(1 / \bigl(\sqrtα \, ρ\bigr)\bigr)$ for regularization parameter $ρ$, giving a positive answer to the open problem posed by Fountoulakis and Yang (COLT 2022). Our faster primitive has the potential to improve a broad range of graph algorithms that rely on local push. For example, substituting our primitive into the ACL framework directly yields faster PageRank-based local graph clustering, and we also develop reductions that lead to faster algorithms for effective resistance estimation. Our main technical contribution is a potential-function analysis of a refinement of the active-set method of Wei and Yang (preprint 2026), which repeatedly invokes an SDD solver on the current active set of nodes and expands the set. We relate the potential decreases over consecutive blocks of expansions to show that the number of expansions is bounded by $\widetilde{O}\bigl(1 / \sqrtα\bigr)$.

Authors: Guanyu Cui, Zhewei Wei, Mingji Yang

We propose a local algorithm that computes an $\varepsilon$-approximate PageRank vector in the sense of Andersen, Chung, and Lang (ACL; Internet Math. 2007) with teleportation parameter $α$ in $\widetilde{O}\bigl(1 / \bigl(\sqrtα \, \varepsilon\bigr)\bigr)$ time with high probability, improving the $O\bigl(1/(α\varepsilon)\bigr)$ running time of their original local push method. Our method also applies to the $\ell_1$-regularized PageRank problem with a running time of $\widetilde{O}\bigl(1 / \bigl(\sqrtα \, ρ\bigr)\bigr)$ for regularization parameter $ρ$, giving a positive answer to the open problem posed by Fountoulakis and Yang (COLT 2022). Our faster primitive has the potential to improve a broad range of graph algorithms that rely on local push. For example, substituting our primitive into the ACL framework directly yields faster PageRank-based local graph clustering, and we also develop reductions that lead to faster algorithms for effective resistance estimation. Our main technical contribution is a potential-function analysis of a refinement of the active-set method of Wei and Yang (preprint 2026), which repeatedly invokes an SDD solver on the current active set of nodes and expands the set. We relate the potential decreases over consecutive blocks of expansions to show that the number of expansions is bounded by $\widetilde{O}\bigl(1 / \sqrtα\bigr)$.

Monday, September 14 2026, 00:00

You are invited: New England Theory Day, October 02

from Hung Le

The UMass Amherst Theory Group is continuing to organize ‘New England Theory Day’ this year, with the goal of bringing together theoretical computer scientists from around the region. It will be an all-day event on October 02 2026, held on UMass’s campus. The day will feature talks by invited speakers, poster and lightening talk sessions for graduate students, and social events. For more details, see: theory.cs.umass.edu/theory-day The registration form: forms.gle/N4bcW5Q5JYyKYgbV9 Registration is free, but we are asking everyone to register by Thursday, September 24 2026.

The UMass Amherst Theory Group is continuing to organize ‘New England Theory Day’ this year, with the goal of bringing together theoretical computer scientists from around the region. It will be an all-day event on October 02 2026, held on UMass’s campus. The day will feature talks by invited speakers, poster and lightening talk sessions for graduate students, and social events.

For more details, see: https://theory.cs.umass.edu/theory-day

The registration form: https://forms.gle/N4bcW5Q5JYyKYgbV9

Registration is free, but we are asking everyone to register by Thursday, September 24 2026.

By Hung Le

Monday, September 14 2026, 00:00

TR26-178 | Optimal Hitting Set Generators via A Potential-Descent Framework | Gonen Krak

from ECCC Papers

We use this framework to construct HSGs for read-once CNFs and read-once CNFs with parities. For formulas on $n$ variables with density at least $\varepsilon$, our generators use $O(\log(n/\varepsilon))$ seed bits. This bound is optimal up to a constant factor. Applying the hitting reduction of Gopalan, Meka, Reingold, Trevisan, and Vadhan gives the same seed bound for general ordered width-3 read-once branching programs. For this class, our construction is the first to achieve optimal dependence on both length and acceptance density. The result provides further evidence supporting the longstanding conjecture $\mathrm{L} = \mathrm{RL}$

Sunday, September 13 2026, 12:23

TR26-177 | Algorithms for Finite Group Epimorphism Testing | Dhara Thakkar, Joshua Grochow, Pranjal Srivastava

from ECCC Papers

The Group Epimorphism Problem (GpEpi) asks, given two finite groups $G_1$ and $G_2$, whether there exists a surjective group homomorphism, or epimorphism, from $G_1$ to $G_2$. When the input groups are given by their multiplication (Cayley) tables, the problem admits a quasipolynomial-time algorithm in general, but little is known about its complexity for structured classes of finite groups. In this paper, we study the computational complexity of GpEpi for several well-studied classes of finite groups. Our main results are polynomial-time epimorphism tests for several classes of groups for which polynomial-time isomorphism testing was previously known: Groups with Abelian normal Hall subgroups with cyclic complement; Groups with (product of) elementary Abelian normal Hall subgroup with elementary Abelian complement; and Groups with some constraints on their Abelian chief factors.

Sunday, September 13 2026, 12:22

TR26-176 | Parallel Kolmogorov Complexity with Connections to Learning Theory and Cryptography | Mandar Juvekar, Marco Carmosino

from ECCC Papers

We introduce a new family of *parallel* time-bounded Kolmogorov complexity measures ($KP^t$). A string $w$ has low $KP^t$ complexity if any individual bit of $w$ can be decompressed from a "short" description using "few" parallel processors within at most $t$ steps. The definition of $KP^t$ uses Parallel Random Access Machines (PRAMs) instead of Turing Machines. Consequently, $KP^t$ is closely related to constant-depth circuit complexity. By varying the PRAM instruction set, we define a variant of $KP^t$ for each standard constant-depth circuit complexity class: $AC^0$, $AC^0[p]$, $ACC^0$, and $TC^0$. We show that for each variant, the $KP^t$ complexity of a string is polynomially related to the minimum size of a circuit in the corresponding circuit class that computes the indexing function for the string. This is directly analogous to the close relationship between the time-bounded Kolmogorov complexity $KT$ and circuit size due to Allender et al. (SIAM J. Comp. 2006). We show that some recently-discovered connections between time-bounded Kolmogorov complexity, learning theory, and cryptography "scale down" to analogous implications for $KP$. 1. If approximating $KP^t$ is easy on average, then functions computed by constant-depth circuits are learnable from random examples over the uniform distribution. On the other hand, if functions computed by constant-depth circuits are learnable from random examples, then $KP^t$ is easy on average to approximate. 2. If approximating $KP^t$ is hard on average, then constant-depth circuits compute secure pseudorandom functions. On the other hand, if constant-depth circuits compute secure pseudorandom functions, then $KP^{t'}$ is hard on average to approximate for some $t' = O(\log n)$. Complementing these implications, we observe that the natural proofs of lower bounds against constant-depth circuit complexity classes $AC^0$ and $AC^0[p]$ imply approximation algorithms for the corresponding variants of $KP^t$. This approximation guarantee is insufficient to obtain new learning algorithms for $AC^0[p]$, but does show that $KP^t$ is strictly easier to approximate than standard time-bounded Kolmogorov complexity (under cryptographic assumptions).

Sunday, September 13 2026, 12:21

TR26-175 | QMA Lower Bounds for Batch Verification via Approximate Degree | Mandar Juvekar, Samuel King, Mark Bun

from ECCC Papers

We study batch verification in QMA query and communication complexity, where the goal is to understand how the resources needed to verify $m$ copies of a Boolean function $f$ depend on $m$. We give a general technique for proving lower bounds on the witness-query tradeoff needed to batch verify a function $f$ in terms of its approximate degree. Applying this technique to an explicit family of DNF formulas $f$, we show that attempting to save even a constant factor on the witness length of the baseline approach to batch verifying $f$ necessitates a large polynomial increase in the query cost. We also obtain new lower bounds on the QMA query complexity of read-once CNF formulas and on the surjectivity and $k$-element distinctness functions. Our lower bounds also lift to give communication analogs of these results.

Sunday, September 13 2026, 12:20

TR26-174 | Frustration Free Stoquastic Local Hamiltonian with Sub-Constant Gap is in $\NP$ | Eshan Chattopadhyay, Oren Renard, Nicholas Spooner

from ECCC Papers

We continue the study of the Stoquastic Local Hamiltonian problem, a physically motivated restriction of the $\QMA$-complete Local Hamiltonian problem \cite{KSV02}. For the $\beta$-gapped, frustration-free case, \citet{BBT06} showed that the problem is $\MA$-complete when $\beta= \frac{1}{\poly(n)}$. \citet{AG19} derandomized this algorithm and proved membership in $\NP$ for constant gap $\beta = \Omega(1)$. An improved algorithm and analysis of \cite{AG19} are presented, establishing membership in $\NP$ even when $\beta = \Omega (\frac{1}{\log\log n})$. We complement our result with an explicit example demonstrating why the analysis does not extend directly to $\beta = o(1/\log\log n)$.

Sunday, September 13 2026, 12:19

TCS+ talk: Wednesday, September 16 — Tselil Schramm, Stanford University

from TCS+ Seminar Series

The next TCS+ talk (and first of the season!) will take place this coming Wednesday, September 16th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Tselil Schramm from Stanford University will give a survey talk about “10 years of the low-degree framework in average-case complexity” (abstract below). You […]

The next TCS+ talk (and first of the season!) will take place this coming Wednesday, September 16th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Tselil Schramm from Stanford University will give a survey talk about “10 years of the low-degree framework in average-case complexity” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: The low-degree framework is a method for studying the computational complexity of average-case (planted) problems. The framework emerged 10 years ago in the context of sum-of-squares lower bounds, and has since been influential in TCS and beyond. In this survey talk I will introduce the framework, then highlight a few results that have emerged in this decade of study.

By plustcs

Saturday, September 12 2026, 07:06

Condorcet Quintets — A Proof from the Book

from Theory Dish: Stanford Blog

Here’s my favorite problem in voting theory. Suppose we have an election in which voters provide ranked preferences over the candidates. For what kk can we always choose kk winners, such that no loser is ranked above all winners by a majority of voters? The question is a riff on Condorcet’s paradox, which famously says that this can’t be done with k=1.k = 1\text{.} Even though the paradox has been around for almost 250 years, this natural twist on it was posed only 15 years ago by Elkind, Lang, and Saffidine (ELS). When I tell someone about this problem, it’s fun to ask them to guess the answer, because it can be a window into the way they think. People well versed in the litany of negative results in voting theory often have the instinct that kk should be nearly as large as the number of candidates m,m\text{,} maybe Ω(m).\Omega(m)\text{.} Friends who work in quantum computing are a little more optimistic, and might suggest O(m)O(\sqrt{m}) is possible. Others who think a lot about graphs (or have recently had the phrase dominating sets whispered in their ear) might guess O(log⁡m),O(\log m)\text{,} which ELS proved in their paper. But it turns out [...]

Here’s my favorite problem in voting theory.

Suppose we have an election in which voters provide ranked preferences over the candidates. For what kk can we always choose kk winners, such that no loser is ranked above all winners by a majority of voters?

The question is a riff on Condorcet’s paradox, which famously says that this can’t be done with k=1.k = 1\text{.} Even though the paradox has been around for almost 250 years, this natural twist on it was posed only 15 years ago by Elkind, Lang, and Saffidine (ELS).

When I tell someone about this problem, it’s fun to ask them to guess the answer, because it can be a window into the way they think. People well versed in the litany of negative results in voting theory often have the instinct that kk should be nearly as large as the number of candidates m,m\text{,} maybe Ω(m).\Omega(m)\text{.} Friends who work in quantum computing are a little more optimistic, and might suggest O(m)O(\sqrt{m}) is possible. Others who think a lot about graphs (or have recently had the phrase dominating sets whispered in their ear) might guess O(log⁡m),O(\log m)\text{,} which ELS proved in their paper.

But it turns out you can do a lot better. You can get away with k=5,k = 5\text{,} no matter the number of candidates.

Before explaining how, a little history. In a paper a couple years ago with Charikar, Lassota, Vetta, and Wang (CLRVW), we pointed out that work by Jiang, Munagala, and Wang (JMW) on approximately stable committees already implies, as a black box, that k=32k = 32 suffices. By generalizing some of their ideas, we got kk down to 6, and Song, Nguyen, and Lin (SNL) improved it to 5. ELS also showed examples which require kk to be at least 3, so the answer is 3, 4, or 5. Figuring out which is optimal remains open.

The upper bound papers (JMW, CLRVW, SNL) all work similarly: construct a “good” distribution over candidates, then use the probabilistic method to show that sampling from it has a chance of producing a Condorcet winning set. JMW use distributions called stable lotteries, introduced by Cheng, Jiang, Munagala, and Wang. CLRVW generalize these to what were later called gg-stable lotteries. SNL use a distribution derived from a Lindahl equilibrium, and give a much simpler proof.

In a recent short note, we explained that since the existence of Lindahl equilibria is proved via Kakutani’s fixed point theorem, peeling off that outer layer makes the proof even easier. But actually, the onion has another layer: if you peel off Kakutani, you get an amazingly simple and elegant proof using Brouwer’s fixed point theorem. This version was suggested by a frontier model (as a peace offering for failing to solve the full problem), but I want to emphasize that it is just a rearrangement of the core ideas from SNL.

So without further ado, here’s the proof.

Suppose we have an election in which, for every set SS of at most kk candidates, there is a candidate aSa_S whom at least an α\alpha fraction of voters rank above every candidate in S.S\text{.} Our goal is to derive the best upper bound on α\alpha as a function of k,k\text{,} and show that for k≥5,k \geq 5\text{,} α<1/2.\alpha \lt 1/2\text{.}

Given a distribution DD over candidates, let D^\widehat{D} be the distribution of aSa_S when S∼DkS \sim D^k (kk iid samples from DD). Because aSa_S is fixed by S,S\text{,} and the probability of each SS is continuous as a function of D,D\text{,} D↦D^D\mapsto \widehat{D} is a continuous map from the set of distributions (a simplex) to itself. Brouwer’s theorem tells us that this map has a fixed point D.D\text{.} In other words, if we sample S∼DkS\sim D^k and set a=aS,a = a_S\text{,} then aa also has distribution DD (though it isn’t independent of SS).

Fix a voter vv with preference ≻v.\succ_v\text{.} To understand the probability that vv prefers aa to all of S,S\text{,} picture their ranking as an interval. Give each candidate a block whose width is their probability under D,D\text{,} and arrange the blocks from left to right, from least to most preferred, filling [0,1].[0, 1]\text{.} Sampling from DD is then just choosing a uniform point on the interval and seeing whose block it lands in.

Voter v's preference visualized on an interval in terms of distribution D.

Now fix some t∈(0,1),t \in (0, 1)\text{,} and let cc be the candidate whose block occupies the point tt on the interval. The blocks above and below cc have total mass at most 1−t1 – t and tt respectively. If a≻vS,a \succ_v S\text{,} then either a≻vc,a \succ_v c\text{,} or c≻vS.c \succ_v S\text{.} Since aa has distribution DD and SS has distribution Dk,D^k\text{,} these two events happen with probability at most 1−t1 – t and tkt^k respectively. By a union bound,

PrS∼Dk⁡[a≻vS]≤Pra∼D⁡[a≻vc]+PrS∼Dk⁡[c≻vS]≤(1−t)+tk.\Pr_{S\sim D^k}[a \succ_v S] \leq \Pr_{a\sim D}[a \succ_v c] + \Pr_{S\sim D^k}[c \succ_v S] \leq (1 – t) + t^k.

Averaging over voters, the left-hand side is at least α,\alpha\text{,} so α≤1−t+tk.\alpha \leq 1 – t + t^k\text{.} To get the strongest bound, set t=k−1/(k−1),t = k^{-1/(k-1)}\text{,} giving α≤1−(k−1)k−k/(k−1),\alpha \leq 1 – (k-1)k^{-k/(k-1)}\text{,} which is less than 1/21/2 for k≥5.k \geq 5\text{.}

Reflecting on points made by Terry Tao and others online, I found myself wondering what would have happened if Elkind, Lang, and Saffidine had posed their question 15 or 20 years later. It feels plausible that a frontier model would have given them a proof like the one above or even solved the problem outright, but maybe there was value in struggling with it more than we needed to.

Without that struggle, we might not have thought to generalize stable lotteries, or developed the visual language for interpreting randomized voting rules that grew alongside that work. Our theory of Lindahl equilibria would be less complete without SNL, which deepened our understanding of how to adapt the idea to settings with ordinal preferences. Their work also helped us understand what our generalization really should have been (in a way that was key to some new work, incidentally related to my last blog post). And selfishly, I would have missed out on the joy of working on a cool problem with brilliant collaborators and friends.

Would that theory have been developed anyway for other problems? What does all of this say about how we should handle what’s coming? Like the question at the start of this blog, I don’t have a complete answer, but there’s an old theorem that I think could be a useful tool:

(Folklore) It’s not just the destination, it’s the journey and the friends we made along the way.

On that note, thanks to Adrian and Alex for introducing me to this problem, and Moses, Kangning, Edith, Emin, Jamie, Thanh, Ariel, and Zohar for many wonderful conversations about it over the years.

(A PDF version of this post is here.)

By Prasanna Ramakrishnan

Friday, September 11 2026, 19:09

9/11 in Berkeley

from Scott Aaronson

Note: Of course I’ve been glued all week to the dramatic developments in AI. I’m working on a post about them. I’m not good at reacting to things in a timely way. So today, I’ll do my post marking the tragedy a quarter-century ago that we all commemorate. Please feel free to share your 9/11 […]

Note: Of course I’ve been glued all week to the dramatic developments in AI. I’m working on a post about them. I’m not good at reacting to things in a timely way. So today, I’ll do my post marking the tragedy a quarter-century ago that we all commemorate. Please feel free to share your 9/11 memories in the comments. Also, Shana Tova to those who celebrate!

The morning of September 11, 2001, I was a second-year PhD student at Berkeley, who woke up late in his dorm room at International House, after a long night spent closing in on the proof of the quantum lower bound for finding collisions.

Rolling over to my laptop, I saw a flurry of weird emails, including one from Prof. Christos Papadimitriou saying that “we’re a community, and we’ll all support each other,” and another from Prof. Luca Trevisan (whose algorithms course I was then TA’ing) saying “on a day like this, it’s impossible to think about algorithms. Class is cancelled.”

Confused, I clicked over to the New York Times and saw the picture of the burning towers, and read numbly about what was already over by the time I’d woken up. I checked in with my mom, made sure relatives and friends in the NYC area were OK. My dad was at a company event in Atlanta, and would need to drive home because of the national grounding of flights.

One of my earliest memories in life, from age 5, is of ascending to the top of the World Trade Center. Growing up an hour’s drive from NYC, it wasn’t an exotic place to me.

I soon learned that one of the dead was Danny Lewin, the ex-IDF captain, theoretical computer scientist, and cofounder of Akamai who had his throat slashed on one of the planes while trying to fight the hijackers, making him the day’s first casualty, even while Akamai’s technology was part of what kept news websites running that day. I’d never met Danny but already knew many people in common with him. A few years later I’d be humbled to win the student paper award that was named in Danny’s memory.

Anyway, at Berkeley on 9/11, I wandered over to Soda Hall just to be with other people. A few students showed up for office hours, wanting help with their algorithms homework, which I found hard to believe, but I did my best to concentrate, as the computer screens around me showed the burning towers.

That evening, I went to a vigil for the victims in Sproul Plaza. But the “vigil,” such as it was, quickly dispensed with mourning and prayers and turned to applauded speeches about how the US must respond with love rather than war, and must turn the other cheek. Meanwhile, a student communist organization was handing out flyers explaining that the victims were mostly “wealthy capitalists and the workers who tried to rescue them.” This while smoke still blanketed NYC and the desperate search for survivors continued. I left the vigil early.

Until that day, I had thought of myself as basically a “leftist,” one whose #1 issue was the existential risk of climate change. Sure, I disagreed with my fellow leftists about issues from nuclear power to gifted education to Israel, but those were just intra-left disputes.

The year before, I had created the website “In Defense Of NaderTrading,” in a desperate attempt to intervene in history and cause Al Gore to become president rather than George W. Bush. When Bush “won,” by the infamous 537 votes in Florida, I considered it a victory for horribleness that would never be surpassed by anything else in my lifetime (ha). I couldn’t imagine any politician who was more the antithesis of everything I believed in than Bush. This view, of course, did not particularly stand out at Berkeley.

In the days after 9/11, though, it became obvious that I could not be a “leftist” in the Berkeley sense. Some of my fellow students felt that Osama bin Laden made a lot of great points, that the attacks were basically justified, and that at any rate, we in Amerikkka had done much worse to provoke them, including by supporting the genocidal settler-colony called “Israel,” which for all we know secretly masterminded the 9/11 attacks anyway (although again, if bin Laden had done them, he would’ve been justified).

Around the same time came the Second Intifada, when a wave of suicide bombings in Israeli buses and pizza parlors and university cafeterias thrilled and energized some Berkeley students to the extent that they took over a Holocaust Remembrance Day event with bullhorns to make it about the Nakba, smashed the windows of the Hillel building, and beat up a couple of students wearing kippot. That was how thoroughly anti-Nazi they were.

I finished my PhD at Berkeley in 2004 having learned about more than quantum computing. I’d learned that, while American academia had pockets that truly were crucial refuges and oases for nerds like me, it also harbored people who would gladly see me and my relatives and my fellow Americans killed for the sake of their ideological vision. And I’d learned that I had my own ideological vision, which was that such people could go fuck themselves.

It deeply pained me to be on the same side of anything as George W. Bush — especially because I knew that 9/11 had happened on his watch, that he had ignored all the warnings, and that he was grossly incompetent to manage the resulting wars against jihadism (just how incompetent, I didn’t know at the time). But as flawed as Bush was, I knew that I wanted to preserve rather than destroy the civilization of which he was a temporary steward. And I think the value and fragility of our civilization is the main lesson from that day that I’d like to convey to my kids, for whom of course 9/11 is just another historical event to learn about in school, like the Boston Tea Party or the Alamo.

By Scott

Friday, September 11 2026, 17:04

Jesús A. De Loera, Ethan X. Fang, Shengtao Guo, Junwei Lu, and Hailun Zheng Proved the Simplex–Cube Conjecture for Simple Polytopes.

from Gil Kalai

Shana Tova Shana Tova (happy new Jewish year) to all our readers! We have just returned to Tel Aviv from the beautiful city of Tiberias, on the Sea of Galilee. The Simplex cube conjecture The simplex–cube conjecture was posed in … Continue reading →

Shana Tova

Shana Tova (happy new Jewish year) to all our readers! We have just returned to Tel Aviv from the beautiful city of Tiberias, on the Sea of Galilee.

The Simplex cube conjecture

The simplex–cube conjecture was posed in my 1990 paper and was among the five problems on convex polytopes discussed in this 2008 post.

Conjecture A. For every $k$ there exists an integer $d(k)$ such that if $P$ is a $d$ -polytope with $d\ge d(k)$ , then $P$ has a $k$ -face which is either a simplex or (combinatorially) a cube.

We denote by $d(k)$ the smallest such integer, if it exists, and otherwise set $d(k) = \infty$ .

A weaker conjecture, which remains open in general, is the following.

Conjecture B. For every positive integer $k$ , there exist an integer $d'(k)$ and a finite collection $\mathcal F_k$ of $k$ -dimensional polytopes such that every $d$ -polytope with $d\ge d'(k)$ has a $k$ -face combinatorially equivalent to a member of $\mathcal F_k$ .

As with $d(k)$ , we let $d'(k)$ denote the smallest possible threshold, and set $d'(k)=\infty$ if no such threshold exists.

Euler’s theorem implies that $latex d′(2)=3$: every 3-polytope has a 2-face that is a triangle, quadrilateral, or pentagon. I proved that $latex d(2)=5$, namely, every 5-polytope has a 2-face that is either a triangle or a quadrilateral. This answered a question of Perles and Shephard from 1967. The bound is sharp: the regular 120-cell is a 4-polytope all of whose 2-faces are pentagons.

On Unavoidable Faces of High-Dimensional Polytopes

I was very happy to learn that Jesús A. De Loera, Ethan X. Fang, Shengtao Guo, Junwei Lu, and Hailun Zheng in their paper On Unavoidable Faces of High Dimensional Polytopes proved Conjecture A for simple polytopes, along with other remarkable results. (A $d$ -polytope is simple if exactly $d$ edges meet at each vertex.)

In my 1990 paper I considered the asymmetric version of the conjecture. Let $\ell,k$ be positive integers, and let $f(\ell,k)$ be the smallest integer $d$ such that every polytope of dimension at least $d$ contains either an $\ell$ -dimensional simplex face or a $k$ -dimensional face combinatorially equivalent to a cube. If no such integer exists, set $f(\ell,k)=\infty$ . The simplex–cube conjecture asserts that

$f(\ell,k)<\infty$

for all $\ell,k$ . The diagonal case is $d(k)=f(k,k)$ .

If $f_s(\ell,k)$ denotes the corresponding threshold restricted to simple polytopes, De Loera, Fang, Guo, Lu, and Zheng proved that $f_s(\ell,k)<\infty$ for every $\ell\ge 2$ and $k\ge 3$ . Moreover, they obtained the explicit bounds:

Theorem (De Loera, Fang, Guo, Lu, and Zheng). For every integer $k\ge3$ :

(i) $f_s(2,k)\le 2k^2-1$ .

(ii) For every integer $\ell\ge3$ ,

$\displaystyle f_s(\ell,k)\le \frac{1}{2}k^2\ell 2^k$ .

The first bound slightly improves my old bound $f_s(2,k)\le 2k^2$ .

The paper contains several other developments. First, the authors obtain substantial new lower bounds for both the general and simple versions of the problem. Second, they make remarkable progress on a related question concerning unavoidable small 3-dimensional faces. Earlier work of Meisinger, Kleinschmidt, and me showed that every rational $d$ -polytope with $d\ge9$ has a 3-face with fewer than 78 vertices or fewer than 78 facets. For dimensions at least 15, the new paper substantially improves the size bound and removes the rationality assumption: every convex polytope in these dimensions has a 3-face with at most 13 facets. The proof uses the nonnegativity of toric $g$ -numbers, inequalities due to Billera and Ehrenborg for the $cd$ -index, and convolution operations. An exact rational certificate involving flag numbers is obtained using linear programming.

By Gil Kalai

Friday, September 11 2026, 06:11

The Computational Complexity of Holant Problems on 4-regular Graphs from the Stable Subgroup Sequence of $SL(2,\mathbb{C})$

Authors: Yuan Huang, Zhiguo Fu

The Holant framework provides a general setting for studying counting problems and includes graph homomorphisms (\#GH) and counting constraint satisfaction problems (\#CSP) as special cases. Over the past twenty years, a series of computational complexity dichotomies have been established for Holant problems, but the classification for complex-valued signatures is still open. The main obstacle is the case in which all signatures have even arity. In this paper, we establish a dichotomy for Holant problems with a complex-valued 4-ary signature, which is a key base case for the full classification of Holant problems. We present a new strategy by introducing Schur's theorem, the classification of finite subgroups of $\mathrm{SL}(2,\mathbb{C})$ and stable subgroup sequences into the proof. These new techniques are of independent interest.

Authors: Yuan Huang, Zhiguo Fu

The Holant framework provides a general setting for studying counting problems and includes graph homomorphisms (\#GH) and counting constraint satisfaction problems (\#CSP) as special cases. Over the past twenty years, a series of computational complexity dichotomies have been established for Holant problems, but the classification for complex-valued signatures is still open. The main obstacle is the case in which all signatures have even arity. In this paper, we establish a dichotomy for Holant problems with a complex-valued 4-ary signature, which is a key base case for the full classification of Holant problems. We present a new strategy by introducing Schur's theorem, the classification of finite subgroups of $\mathrm{SL}(2,\mathbb{C})$ and stable subgroup sequences into the proof. These new techniques are of independent interest.

Friday, September 11 2026, 00:00

Online Treasure Hunt in Vertex-Permuted Dynamic Rings

Authors: Kamran Ayoubi, Bernard Mans, Lata Narayanan

We study the problem of treasure hunt by a group of $k \geq 1$ agents in vertex-permuted dynamic rings (VP). In this model, the $n$ vertices remain on a ring but are permuted at each time step. We first show that treasure hunt is impossible for any $k \leq n-3$ agents, if there are no restrictions on the sequence of permutations used in the dynamic ring. We then study the $VP(δ)$ setting, in which for every pair $i, j$ of vertices, the edge $(i, j)$ is guaranteed to appear within $δ$ steps. We show that the class $VP(δ)$ is feasible only for $δ\geq \left\lceil \frac{n-1}{2}\right\rceil$. For the one-agent case, we show a tight bound of $Θ(δn)$ on the worst-case search time as well as competitive ratio of any online algorithm for treasure hunt, provided $δ\geq 2n$. We then give an optimal algorithm for $k$ agents, thereby showing that $k$ agents can obtain a speedup of $k$ on the worst-case search time. Finally, in the R-VP setting, in which in every step, the vertices are arranged as a ring according to a random permutation, we show that treasure hunt takes expected $Θ(n)$ steps against an oblivious adversary and $Θ(n \log n)$ steps against an adaptive adversary.

Authors: Kamran Ayoubi, Bernard Mans, Lata Narayanan

We study the problem of treasure hunt by a group of $k \geq 1$ agents in vertex-permuted dynamic rings (VP). In this model, the $n$ vertices remain on a ring but are permuted at each time step. We first show that treasure hunt is impossible for any $k \leq n-3$ agents, if there are no restrictions on the sequence of permutations used in the dynamic ring. We then study the $VP(δ)$ setting, in which for every pair $i, j$ of vertices, the edge $(i, j)$ is guaranteed to appear within $δ$ steps. We show that the class $VP(δ)$ is feasible only for $δ\geq \left\lceil \frac{n-1}{2}\right\rceil$. For the one-agent case, we show a tight bound of $Θ(δn)$ on the worst-case search time as well as competitive ratio of any online algorithm for treasure hunt, provided $δ\geq 2n$. We then give an optimal algorithm for $k$ agents, thereby showing that $k$ agents can obtain a speedup of $k$ on the worst-case search time. Finally, in the R-VP setting, in which in every step, the vertices are arranged as a ring according to a random permutation, we show that treasure hunt takes expected $Θ(n)$ steps against an oblivious adversary and $Θ(n \log n)$ steps against an adaptive adversary.

Friday, September 11 2026, 00:00

The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem

Authors: Mikhail Mints, Eric R. Anschuetz

In this work, we analyze the average-case hardness of approximation for the Quantum Hypergraph Max-Cut problem using the theoretical framework of the Quantum Overlap Gap Property (QOGP). We establish two main results. Our first result applies to a wide class of stable quantum algorithms, satisfying a Lipschitz property with respect to the quantum Wasserstein distance of order $2$. We show a weak hardness result, demonstrating that for any Lipschitz constant $L$, there is some $k$ such that $L$-stable algorithms cannot approximate the optimal solution to Quantum Hypergraph Max-Cut on $k$-uniform hypergraphs in the average case. Additionally, we establish a strong hardness result where $k$ is independent of $L$, but only for a more restricted class of local quantum algorithms defined using the quantum Wasserstein distance of order $\infty$. We apply these results to establish concrete depth lower bounds for popular quantum algorithms for preparing near-optimal states for this problem.

Authors: Mikhail Mints, Eric R. Anschuetz

In this work, we analyze the average-case hardness of approximation for the Quantum Hypergraph Max-Cut problem using the theoretical framework of the Quantum Overlap Gap Property (QOGP). We establish two main results. Our first result applies to a wide class of stable quantum algorithms, satisfying a Lipschitz property with respect to the quantum Wasserstein distance of order $2$. We show a weak hardness result, demonstrating that for any Lipschitz constant $L$, there is some $k$ such that $L$-stable algorithms cannot approximate the optimal solution to Quantum Hypergraph Max-Cut on $k$-uniform hypergraphs in the average case. Additionally, we establish a strong hardness result where $k$ is independent of $L$, but only for a more restricted class of local quantum algorithms defined using the quantum Wasserstein distance of order $\infty$. We apply these results to establish concrete depth lower bounds for popular quantum algorithms for preparing near-optimal states for this problem.

Friday, September 11 2026, 00:00

PureSuperQMA(exp) = BellPureSymQMA(poly) = QMA via Dimension-Free Bosonic Argmax

Authors: William Gay, Fernando Granha Jeronimo, Lenny Liu, Itai Leigh, Pei Wu, Haochen Xu

Pure-state consistency problems naturally lead to quantum proof systems in which a single pure witness must satisfy many acceptance constraints. The corresponding class $\mathsf{PureSuperQMA}$ was previously known to lie between $\mathsf{QMA}$ and $\mathsf{QMA}(2)$, and Kamminga and Rudolph (ITCS'26) conjectured that both containments are strict. In this paper, we prove the following surprising complexity collapses $$ \mathsf{QMA} = \mathsf{PureSuperQMA} = \mathsf{PureSuperQMA}(\text{exp}) = \mathsf{BellPureSymQMA}(\text{poly}) $$ Here $\mathsf{PureSuperQMA}(\text{exp})$ allows exponentially many checks which are uniformly indexed and efficiently generated, while requiring an inverse-polynomial violation margin and an inverse-polynomial fraction of violated checks for the NO cases. $\mathsf{BellPureSymQMA}(\text{poly})$ is a related model that requires the prover to give the verifier polynomially many copies of a pure state, which the verifier measures separately with logarithmic output length for each local measurement, before processing the outcomes jointly. The main technical ingredient is a dimension-free stability bound for symmetric tensor states. Our simulations use polynomially many witness registers and combine a random-pair SWAP test with a permutation-invariant lift of the original verification procedure. The key step is to show that, on the symmetric subspace, the extremal verification value is close to that of some tensor-power witness with dimension-independent error. Applying this argument to the two verification models yields both simulations. As a consequence, exact $k$-local pure-state consistency is $\mathsf{QMA}$-complete for every fixed $k\ge2$, and so are the corresponding exact bosonic and fermionic pure $N$-representability problems.

Authors: William Gay, Fernando Granha Jeronimo, Lenny Liu, Itai Leigh, Pei Wu, Haochen Xu

Pure-state consistency problems naturally lead to quantum proof systems in which a single pure witness must satisfy many acceptance constraints. The corresponding class $\mathsf{PureSuperQMA}$ was previously known to lie between $\mathsf{QMA}$ and $\mathsf{QMA}(2)$, and Kamminga and Rudolph (ITCS'26) conjectured that both containments are strict. In this paper, we prove the following surprising complexity collapses $$ \mathsf{QMA} = \mathsf{PureSuperQMA} = \mathsf{PureSuperQMA}(\text{exp}) = \mathsf{BellPureSymQMA}(\text{poly}) $$ Here $\mathsf{PureSuperQMA}(\text{exp})$ allows exponentially many checks which are uniformly indexed and efficiently generated, while requiring an inverse-polynomial violation margin and an inverse-polynomial fraction of violated checks for the NO cases. $\mathsf{BellPureSymQMA}(\text{poly})$ is a related model that requires the prover to give the verifier polynomially many copies of a pure state, which the verifier measures separately with logarithmic output length for each local measurement, before processing the outcomes jointly. The main technical ingredient is a dimension-free stability bound for symmetric tensor states. Our simulations use polynomially many witness registers and combine a random-pair SWAP test with a permutation-invariant lift of the original verification procedure. The key step is to show that, on the symmetric subspace, the extremal verification value is close to that of some tensor-power witness with dimension-independent error. Applying this argument to the two verification models yields both simulations. As a consequence, exact $k$-local pure-state consistency is $\mathsf{QMA}$-complete for every fixed $k\ge2$, and so are the corresponding exact bosonic and fermionic pure $N$-representability problems.

Friday, September 11 2026, 00:00

Oracle Separations in the Fourier Hierarchy

Authors: Atul Mantri

The Fourier hierarchy $\mathrm{FH}_0\subseteq\mathrm{FH}_1\subseteq\mathrm{FH}_2\subseteq\cdots$, introduced by Shi (TCS 2005), measures a quantum computation by the number of Hadamard layers it uses. Between two layers the circuit may permute basis states and attach phases, but it may not create superposition; the layers are its only source of interference. The first level is exactly $\mathrm{BPP}$, while the second already solves Simon's problem and, through phase estimation, factors integers. Shi conjectured that every additional layer strictly increases computational power, and asked, as a first step, for oracle separations between consecutive levels. To our knowledge, the question was open at every level $k\ge2$. We prove that for every constant $k\ge2$ there is an oracle relative to which $\mathrm{FH}_k\subsetneq\mathrm{FH}_{k+1}$. The separating problem is built from Forrelation (Aaronson and Ambainis, STOC 2015): the level above solves it with a constant number of queries, whereas at level $k$ it stays hard even for circuits making exponentially many queries. This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle, which writes its answer into a register. The two are not interchangeable: relative to an oracle, the standard oracle is strictly more powerful at the same number of layers. We also separate the union of all the levels from $\mathrm{BQP}$ relative to an oracle. The lower bounds rest on a structural property of the hierarchy: the number of Hadamard layers limits how adaptively a circuit can query its oracle. With a phase oracle, a circuit with $k$ layers is reproduced exactly by an algorithm making only $k-1$ rounds of parallel queries, which brings known lower bounds for such algorithms to bear. The standard oracle lets a circuit branch on earlier answers, and that case needs a separate argument.

Authors: Atul Mantri

The Fourier hierarchy $\mathrm{FH}_0\subseteq\mathrm{FH}_1\subseteq\mathrm{FH}_2\subseteq\cdots$, introduced by Shi (TCS 2005), measures a quantum computation by the number of Hadamard layers it uses. Between two layers the circuit may permute basis states and attach phases, but it may not create superposition; the layers are its only source of interference. The first level is exactly $\mathrm{BPP}$, while the second already solves Simon's problem and, through phase estimation, factors integers. Shi conjectured that every additional layer strictly increases computational power, and asked, as a first step, for oracle separations between consecutive levels. To our knowledge, the question was open at every level $k\ge2$. We prove that for every constant $k\ge2$ there is an oracle relative to which $\mathrm{FH}_k\subsetneq\mathrm{FH}_{k+1}$. The separating problem is built from Forrelation (Aaronson and Ambainis, STOC 2015): the level above solves it with a constant number of queries, whereas at level $k$ it stays hard even for circuits making exponentially many queries. This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle, which writes its answer into a register. The two are not interchangeable: relative to an oracle, the standard oracle is strictly more powerful at the same number of layers. We also separate the union of all the levels from $\mathrm{BQP}$ relative to an oracle. The lower bounds rest on a structural property of the hierarchy: the number of Hadamard layers limits how adaptively a circuit can query its oracle. With a phase oracle, a circuit with $k$ layers is reproduced exactly by an algorithm making only $k-1$ rounds of parallel queries, which brings known lower bounds for such algorithms to bear. The standard oracle lets a circuit branch on earlier answers, and that case needs a separate argument.

Friday, September 11 2026, 00:00

Topology inside NC$^1$

Authors: Eric Allender, Samir Datta, Arsenii Karnaukhov, Sambuddha Roy, Alexander Shekhovstov

We show that ACC$^0$ is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC$^0$. Thus polylogarithmic genus provides no additional computational power in this model. We consider other generalizations of planarity, including crossing number and thickness. We show that constant-width circuits of polynomial size and thickness two already suffice to capture all of NC$^1$.

Authors: Eric Allender, Samir Datta, Arsenii Karnaukhov, Sambuddha Roy, Alexander Shekhovstov

We show that ACC$^0$ is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC$^0$. Thus polylogarithmic genus provides no additional computational power in this model. We consider other generalizations of planarity, including crossing number and thickness. We show that constant-width circuits of polynomial size and thickness two already suffice to capture all of NC$^1$.

Friday, September 11 2026, 00:00

Some results on Archdeacon's conjecture for rotation systems

Authors: Arahat Chikkatur, Ji Zeng

A rotation system on $n$ elements assigns to each element a cyclic order of the other $n-1$ elements. A four-element subset is non-planar if its induced rotation system cannot be realized by a crossing-free drawing of $K_4$. As a combinatorial strengthening of Hill's conjecture on the crossing number of the complete graph, Archdeacon conjectured that every rotation system on $n$ elements has at least $H(n)=\frac{1}{4} \lfloor\frac {n}{2}\rfloor \lfloor\frac{n-1}{2}\rfloor \lfloor\frac{n-2}{2}\rfloor \lfloor\frac{n-3}{2}\rfloor$ non-planar four-element subsets. We computationally verify Archdeacon's conjecture for $n\leq 10$ and show that every extremal rotation system in these orders is realizable by a simple drawing. With computer assistance, we prove that every rotation system on $n$ elements has at least $(8/9 - o(1)) H(n)$ non-planar four-element subsets. We also present a proof by hand for a weaker lower bound of $(2/3-o(1)) H(n)$. Finally, extending recent work of Felsner on antipodal pairs in drawings, we show that Archdeacon's conjecture holds for antipodally shellable rotation systems.

Authors: Arahat Chikkatur, Ji Zeng

A rotation system on $n$ elements assigns to each element a cyclic order of the other $n-1$ elements. A four-element subset is non-planar if its induced rotation system cannot be realized by a crossing-free drawing of $K_4$. As a combinatorial strengthening of Hill's conjecture on the crossing number of the complete graph, Archdeacon conjectured that every rotation system on $n$ elements has at least $H(n)=\frac{1}{4} \lfloor\frac {n}{2}\rfloor \lfloor\frac{n-1}{2}\rfloor \lfloor\frac{n-2}{2}\rfloor \lfloor\frac{n-3}{2}\rfloor$ non-planar four-element subsets. We computationally verify Archdeacon's conjecture for $n\leq 10$ and show that every extremal rotation system in these orders is realizable by a simple drawing. With computer assistance, we prove that every rotation system on $n$ elements has at least $(8/9 - o(1)) H(n)$ non-planar four-element subsets. We also present a proof by hand for a weaker lower bound of $(2/3-o(1)) H(n)$. Finally, extending recent work of Felsner on antipodal pairs in drawings, we show that Archdeacon's conjecture holds for antipodally shellable rotation systems.

Friday, September 11 2026, 00:00

Learn the Solid, Not the File: Canonical Inputs for Neural Networks on CAD Boundary Representations

Authors: Heinrich Jiang, Hager Yasser Mohamed, Alexander Hitt, Valeriia Lomakina, Henning Jiang, Jennifer Jang

Boundary representation (B-rep) is the standard format used by modern CAD systems for parametric 3D models. It turns out, the exact same solid can be represented by different B-reps: for example, two engineers using different operations, a geometry kernel rebuilding the file, and an export setting repartitioning faces will lead to different B-reps even though the underlying solid remains the same. We show that existing B-rep encoders are not robust to variation in the B-rep with the same solid on perturbations applied to standard benchmarks, naturally occurring variations inherent to CAD software, and differences in how designers model the same part via a human dataset we created in FreeCAD. The performance of popular B-rep encoders often collapses catastrophically. We propose the canonical region graph, an input representation whose nodes, features and coordinate frame are derived from the solid itself and show theoretical invariance guarantees on repartitioning and rigid motions. It matches the strongest baseline on standard benchmarks, and is stable under every perturbation we test.

Authors: Heinrich Jiang, Hager Yasser Mohamed, Alexander Hitt, Valeriia Lomakina, Henning Jiang, Jennifer Jang

Boundary representation (B-rep) is the standard format used by modern CAD systems for parametric 3D models. It turns out, the exact same solid can be represented by different B-reps: for example, two engineers using different operations, a geometry kernel rebuilding the file, and an export setting repartitioning faces will lead to different B-reps even though the underlying solid remains the same. We show that existing B-rep encoders are not robust to variation in the B-rep with the same solid on perturbations applied to standard benchmarks, naturally occurring variations inherent to CAD software, and differences in how designers model the same part via a human dataset we created in FreeCAD. The performance of popular B-rep encoders often collapses catastrophically. We propose the canonical region graph, an input representation whose nodes, features and coordinate frame are derived from the solid itself and show theoretical invariance guarantees on repartitioning and rigid motions. It matches the strongest baseline on standard benchmarks, and is stable under every perturbation we test.

Friday, September 11 2026, 00:00

Almost Linear Universal Point Sets for Planar Graphs

Authors: Taylor Gordon

A point set is universal for planar graphs on $n$ vertices if every such graph has a straight-line drawing without crossings whose vertices belong to the set. We construct universal point sets of size $n^{1+o(1)}$, improving the previous quadratic upper bound. Our construction uses the reduction of Bannister, Cheng, Devanny, and Eppstein from universal point sets to superpatterns for $213$-avoiding permutations. We represent these permutations by ordered rooted forests and construct a small family of intervals containing every such forest. The result follows from a straightforward bound on the size of the family of intervals. GPT-6 Astra assisted in developing the construction and proof.

Authors: Taylor Gordon

A point set is universal for planar graphs on $n$ vertices if every such graph has a straight-line drawing without crossings whose vertices belong to the set. We construct universal point sets of size $n^{1+o(1)}$, improving the previous quadratic upper bound. Our construction uses the reduction of Bannister, Cheng, Devanny, and Eppstein from universal point sets to superpatterns for $213$-avoiding permutations. We represent these permutations by ordered rooted forests and construct a small family of intervals containing every such forest. The result follows from a straightforward bound on the size of the family of intervals. GPT-6 Astra assisted in developing the construction and proof.

Friday, September 11 2026, 00:00

Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor

Authors: Édouard Bonnet, Yeonsu Chang

We show that there is a fixed planar graph $H$, namely the $5 \times 5$ grid, such that Max Independent Set remains NP-hard in $H$-induced-minor-free graphs. This refutes the Dallard--Milanič--Štorgel conjecture and a weakening of it by Gartland and Lokshtanov, and by Korhonen.

Authors: Édouard Bonnet, Yeonsu Chang

We show that there is a fixed planar graph $H$, namely the $5 \times 5$ grid, such that Max Independent Set remains NP-hard in $H$-induced-minor-free graphs. This refutes the Dallard--Milanič--Štorgel conjecture and a weakening of it by Gartland and Lokshtanov, and by Korhonen.

Friday, September 11 2026, 00:00

Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry

Authors: Frédéric Magniez, Sebastian Zur

How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function $f:[N]\to [N]$, the BHT algorithm finds a collision using $O(N^{1/3})$ queries and a quantumly accessible classical table containing $O(N^{1/3})$ input-output pairs, whereas a logarithmic-space Grover search uses $O(\sqrt N)$ queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function $f$'s output labels as interchangeable. We prove that such algorithm that makes $T$ queries, uses $S$ qubits, and finds a collision in a uniformly random function $f:[M]\to [N]$ with constant probability satisfies $$T=Ω(N^{1/3}) \qquad\text{and}\qquad T^2S=Ω(N\log N).$$ For the setting where $M=N$, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on $f: [n] \to [n^2]$ must satisfy $$T=Ω(n^{2/3}) \qquad\text{and}\qquad T^2S=Ω(n^2\log n),$$ matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using $S$ qubits can effectively retain information about only $O(S/\log N)$ collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.

Authors: Frédéric Magniez, Sebastian Zur

How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function $f:[N]\to [N]$, the BHT algorithm finds a collision using $O(N^{1/3})$ queries and a quantumly accessible classical table containing $O(N^{1/3})$ input-output pairs, whereas a logarithmic-space Grover search uses $O(\sqrt N)$ queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function $f$'s output labels as interchangeable. We prove that such algorithm that makes $T$ queries, uses $S$ qubits, and finds a collision in a uniformly random function $f:[M]\to [N]$ with constant probability satisfies $$T=Ω(N^{1/3}) \qquad\text{and}\qquad T^2S=Ω(N\log N).$$ For the setting where $M=N$, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on $f: [n] \to [n^2]$ must satisfy $$T=Ω(n^{2/3}) \qquad\text{and}\qquad T^2S=Ω(n^2\log n),$$ matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using $S$ qubits can effectively retain information about only $O(S/\log N)$ collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.

Friday, September 11 2026, 00:00

Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions

Authors: Rahul Vaze

Convex Optimization with Nested Evolving Feasible Sets (CONES)} was introduced in \cite{CONESVaze} where the objective function $f$ remains fixed but the feasible region evolves over time as a nested sequence $S_1 \supseteq S_2 \supseteq \cdots \supseteq S_T$. The goal of an online algorithm is to simultaneously minimize the regret with respect to hindsight static optimal benchmark and the total movement cost $M_\cA(T)$ while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known \emph{nested convex body chasing} (NCBC). In this paper, we extend CONES to allow for loss functions $f_t'$s to also change over time. When all loss functions are convex, we show that the projected proximal algorithm achieves $O(T^{1-β}), O(T^β)$ simultaneous regret and movement cost, respectively, for any $β\in [0,1)$, over a time horizon of $T$. We also show that any {\it weakly adaptive} online algorithm with $O(T^β)$ regret has a movement cost of $Ω\left(T^{\frac{1-β}{2}}\right)$ for any $β\in [0,1)$. When all loss functions are strongly convex, we show that the projected proximal algorithm simultaneously achieves $O(1)$ regret and a movement cost of $O(\log T)$. To complement this, we show that any online algorithm with sublinear {\it anytime} regret has a movement cost of $Ω\left(\log T\right)$.

Authors: Rahul Vaze

Convex Optimization with Nested Evolving Feasible Sets (CONES)} was introduced in \cite{CONESVaze} where the objective function $f$ remains fixed but the feasible region evolves over time as a nested sequence $S_1 \supseteq S_2 \supseteq \cdots \supseteq S_T$. The goal of an online algorithm is to simultaneously minimize the regret with respect to hindsight static optimal benchmark and the total movement cost $M_\cA(T)$ while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known \emph{nested convex body chasing} (NCBC). In this paper, we extend CONES to allow for loss functions $f_t'$s to also change over time. When all loss functions are convex, we show that the projected proximal algorithm achieves $O(T^{1-β}), O(T^β)$ simultaneous regret and movement cost, respectively, for any $β\in [0,1)$, over a time horizon of $T$. We also show that any {\it weakly adaptive} online algorithm with $O(T^β)$ regret has a movement cost of $Ω\left(T^{\frac{1-β}{2}}\right)$ for any $β\in [0,1)$. When all loss functions are strongly convex, we show that the projected proximal algorithm simultaneously achieves $O(1)$ regret and a movement cost of $O(\log T)$. To complement this, we show that any online algorithm with sublinear {\it anytime} regret has a movement cost of $Ω\left(\log T\right)$.

Friday, September 11 2026, 00:00

Single-Exponential Algorithms and a Polynomial Kernel for Strong Connectivity Augmentation

Authors: Tomohiro Koana, Soh Kumabe

Strong Connectivity Augmentation (SCA) asks whether a directed acyclic graph can be made strongly connected by adding at most $k$ prescribed links whose total weight is within a given budget. Klinkby, Misra, and Saurabh (SODA 2021) gave an $O^*(2^{O(k\log k)})$-time algorithm and asked whether the problem admits a single-exponential parameterized algorithm and a polynomial kernel. We answer both questions affirmatively: SCA can be solved in $O^*(9^k)$ time and admits a polynomial kernel with $O(k^4)$ vertices and $O(k^{16})$ bits. For unweighted SCA, we obtain $O^*(4^k)$ time and a kernel with $O(k^3)$ vertices. Our algorithms are based on a particularly simple reduction to Strongly Connected Spanning Subgraph with two edge costs.

Authors: Tomohiro Koana, Soh Kumabe

Strong Connectivity Augmentation (SCA) asks whether a directed acyclic graph can be made strongly connected by adding at most $k$ prescribed links whose total weight is within a given budget. Klinkby, Misra, and Saurabh (SODA 2021) gave an $O^*(2^{O(k\log k)})$-time algorithm and asked whether the problem admits a single-exponential parameterized algorithm and a polynomial kernel. We answer both questions affirmatively: SCA can be solved in $O^*(9^k)$ time and admits a polynomial kernel with $O(k^4)$ vertices and $O(k^{16})$ bits. For unweighted SCA, we obtain $O^*(4^k)$ time and a kernel with $O(k^3)$ vertices. Our algorithms are based on a particularly simple reduction to Strongly Connected Spanning Subgraph with two edge costs.

Friday, September 11 2026, 00:00

A deterministic $(1+\varepsilon)^n$ approximation for the permanent of a nonnegative matrix

Authors: Dingding Dong, Vishesh Jain

For every fixed $0<\varepsilon\le1$, we give a deterministic strongly polynomial algorithm that, given a nonnegative matrix $A\in\mathbb{R}_{\ge0}^{n\times n}$, returns $Q$ satisfying $\operatorname{per} A\le Q\le(1+\varepsilon)^n\operatorname{per} A$.

Authors: Dingding Dong, Vishesh Jain

For every fixed $0<\varepsilon\le1$, we give a deterministic strongly polynomial algorithm that, given a nonnegative matrix $A\in\mathbb{R}_{\ge0}^{n\times n}$, returns $Q$ satisfying $\operatorname{per} A\le Q\le(1+\varepsilon)^n\operatorname{per} A$.

Friday, September 11 2026, 00:00

Quasi-Monte Carlo Beyond Hardy-Krause II: $(1 + \varepsilon)n$ Samples Suffice

Authors: Ekene Ezeunala, Agastya Vibhuti Jha, Haotian Jiang

Numerical integration studies how well one can estimate the integral of a function $f$ over $[0,1)^d$ using $n$ sample points. The two classical methods, Monte Carlo (MC) and quasi-Monte Carlo (QMC), have complementary strengths and weaknesses, and a fundamental question is to design an approach that combines the benefits of both. Recently, building on the transference principle in discrepancy theory, Bansal and Jiang~\cite{BJ25a} gave a randomized QMC method that bridges MC and QMC guarantees using only i.i.d.\ samples. Their method also goes beyond the classical Koksma--Hlawka inequality: it achieves integration error $\widetilde{O}_d(σ_{\mathsf{SO}}(f)/n)$, where the smoothed-out variation $σ_{\mathsf{SO}}(f)$ can be substantially smaller than the Hardy--Krause variation that governs the classical bound. However, their algorithm requires $n^2$ i.i.d.\ samples as input, and this quadratic blowup is inherent to any method based on the transference principle. In this work, we bypass the quadratic blowup: for any constant $\varepsilon > 0$, we show that $(1+\varepsilon)n$ i.i.d.\ samples suffice to both obtain the beyond-Hardy--Krause guarantee of~\cite{BJ25a}, resolving an open problem posed there, and to produce low-discrepancy point sequences. Our algorithms are variants of the online Haar-thinning method of Dwivedi, Feldheim, Gurel-Gurevich, and Ramdas~\cite{DFG+19}.

Authors: Ekene Ezeunala, Agastya Vibhuti Jha, Haotian Jiang

Numerical integration studies how well one can estimate the integral of a function $f$ over $[0,1)^d$ using $n$ sample points. The two classical methods, Monte Carlo (MC) and quasi-Monte Carlo (QMC), have complementary strengths and weaknesses, and a fundamental question is to design an approach that combines the benefits of both. Recently, building on the transference principle in discrepancy theory, Bansal and Jiang~\cite{BJ25a} gave a randomized QMC method that bridges MC and QMC guarantees using only i.i.d.\ samples. Their method also goes beyond the classical Koksma--Hlawka inequality: it achieves integration error $\widetilde{O}_d(σ_{\mathsf{SO}}(f)/n)$, where the smoothed-out variation $σ_{\mathsf{SO}}(f)$ can be substantially smaller than the Hardy--Krause variation that governs the classical bound. However, their algorithm requires $n^2$ i.i.d.\ samples as input, and this quadratic blowup is inherent to any method based on the transference principle. In this work, we bypass the quadratic blowup: for any constant $\varepsilon > 0$, we show that $(1+\varepsilon)n$ i.i.d.\ samples suffice to both obtain the beyond-Hardy--Krause guarantee of~\cite{BJ25a}, resolving an open problem posed there, and to produce low-discrepancy point sequences. Our algorithms are variants of the online Haar-thinning method of Dwivedi, Feldheim, Gurel-Gurevich, and Ramdas~\cite{DFG+19}.

Friday, September 11 2026, 00:00

Navigating Small-World Networks with Distance Predictions

Authors: Ladan Kian, Ming Ming Tan, Dariusz Kowalski

The small-world phenomenon was given an algorithmic foundation by Kleinberg, who showed that in an augmented $k$-dimensional lattice a decentralized greedy algorithm delivers a message in $O(\log^2 n)$ expected steps. We study predicted-greedy routing, in which a mobile agent forwarding the message moves at each step to the neighbor minimizing a noisy $(\varepsilon,δ)$-prediction of its distance to the target, redrawn at every step from an oracle conditioned on the full routing history. Two cases arise from what this agent can observe. An agent with the coordinate awareness can still compute lattice distance exactly, but not graph distance in the shortcut-augmented network, since that depends on the shortcuts of nodes it has not yet visited; given an $(\varepsilon,δ)$-prediction of graph distance, information the classical model never supplies, it achieves expected delivery time $O(\log n/(1-4k\varepsilonδ))$, an asymptotic improvement over $Θ(\log^2 n)$. An agent with no coordinate awareness at all, the natural model for a privacy-preserving network whose nodes never disclose their coordinates, cannot compute even lattice distance; given an $(\varepsilon,δ)$-prediction of lattice distance instead, it still reaches the target in $O(n/(1-4k\varepsilonδ))$ expected steps. Together these results show that a modest amount of predicted information, of the right kind, is enough to accelerate decentralized routing well below Kleinberg's classical bound, and that even when nodes reveal no coordinates at all, reliable delivery remains achievable.

Authors: Ladan Kian, Ming Ming Tan, Dariusz Kowalski

The small-world phenomenon was given an algorithmic foundation by Kleinberg, who showed that in an augmented $k$-dimensional lattice a decentralized greedy algorithm delivers a message in $O(\log^2 n)$ expected steps. We study predicted-greedy routing, in which a mobile agent forwarding the message moves at each step to the neighbor minimizing a noisy $(\varepsilon,δ)$-prediction of its distance to the target, redrawn at every step from an oracle conditioned on the full routing history. Two cases arise from what this agent can observe. An agent with the coordinate awareness can still compute lattice distance exactly, but not graph distance in the shortcut-augmented network, since that depends on the shortcuts of nodes it has not yet visited; given an $(\varepsilon,δ)$-prediction of graph distance, information the classical model never supplies, it achieves expected delivery time $O(\log n/(1-4k\varepsilonδ))$, an asymptotic improvement over $Θ(\log^2 n)$. An agent with no coordinate awareness at all, the natural model for a privacy-preserving network whose nodes never disclose their coordinates, cannot compute even lattice distance; given an $(\varepsilon,δ)$-prediction of lattice distance instead, it still reaches the target in $O(n/(1-4k\varepsilonδ))$ expected steps. Together these results show that a modest amount of predicted information, of the right kind, is enough to accelerate decentralized routing well below Kleinberg's classical bound, and that even when nodes reveal no coordinates at all, reliable delivery remains achievable.

Friday, September 11 2026, 00:00

Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks

Authors: Jacob Imola, Rasmus Pagh, Lukas Retschmeier

This paper studies fundamental graph optimization problems under differential privacy (DP) and shows new, reconstruction-based lower bounds. We consider a graph $G = (V, E, \vec{w})$ where the vertex set $V$ and edges $E$ are public and the weights $\mathbf{w}:E\rightarrow \mathbb{R}$ must be kept differentially private under an $\ell_1$ neighboring relation. For the problems of releasing a minimum-weight spanning tree and a minimum-weight perfect matching, we show new, tight error bounds of $Ω(n\cdot\log(m/n)/ε)$ on worst-case graphs with $n$ vertices and $m>2n$ edges. The upper bounds are known pure DP algorithms while the new lower bound holds even under approximate $(\varepsilon,δ)$-DP as long as $δ\leq (n/m)^{Ω(1)}$. Our lower bounds improve the $Ω(n/ε)$ lower bounds of Sealfon (PODS~'16). The fact that approximate DP does not reduce error for MST under the $\ell_1$ neighboring relation contrasts with the recent upper bound of Pagh et al. (PODS~'25) which shows that approximate DP allows much better error under the $\ell_\infty$ neighboring relation. Going beyond worst-case graphs, we give lower bounds for large families of sparse graphs with expansion properties. We show a lower bound of $Ω(n / ε)$ for the minimum spanning tree for any graph where the minimum cut is at least $Ω(\log(n))$. Finally, we consider the problem of private hierarchical clustering under Dasgupta's cost function (STOC~'16) and show the first approximate DP lower bound parameterized by the minimum weight of a balanced cut. This extends lower bounds of Deng et al. (ICLR~'25) to general graphs and to approximate DP.

Authors: Jacob Imola, Rasmus Pagh, Lukas Retschmeier

This paper studies fundamental graph optimization problems under differential privacy (DP) and shows new, reconstruction-based lower bounds. We consider a graph $G = (V, E, \vec{w})$ where the vertex set $V$ and edges $E$ are public and the weights $\mathbf{w}:E\rightarrow \mathbb{R}$ must be kept differentially private under an $\ell_1$ neighboring relation. For the problems of releasing a minimum-weight spanning tree and a minimum-weight perfect matching, we show new, tight error bounds of $Ω(n\cdot\log(m/n)/ε)$ on worst-case graphs with $n$ vertices and $m>2n$ edges. The upper bounds are known pure DP algorithms while the new lower bound holds even under approximate $(\varepsilon,δ)$-DP as long as $δ\leq (n/m)^{Ω(1)}$. Our lower bounds improve the $Ω(n/ε)$ lower bounds of Sealfon (PODS~'16). The fact that approximate DP does not reduce error for MST under the $\ell_1$ neighboring relation contrasts with the recent upper bound of Pagh et al. (PODS~'25) which shows that approximate DP allows much better error under the $\ell_\infty$ neighboring relation. Going beyond worst-case graphs, we give lower bounds for large families of sparse graphs with expansion properties. We show a lower bound of $Ω(n / ε)$ for the minimum spanning tree for any graph where the minimum cut is at least $Ω(\log(n))$. Finally, we consider the problem of private hierarchical clustering under Dasgupta's cost function (STOC~'16) and show the first approximate DP lower bound parameterized by the minimum weight of a balanced cut. This extends lower bounds of Deng et al. (ICLR~'25) to general graphs and to approximate DP.

Friday, September 11 2026, 00:00

Free-Probabilistic State Evolution and Random Matrix Discrepancy

Authors: August Y. Chen, Ahmed El Alaoui

Let $A_1,\ldots,A_n$ be independent $d \times d$ real symmetric Gaussian random matrices, and consider the linear operator $A(x) = n^{-1/2}\sum_{i=1}^n x_i A_i$, $x\in \mathbb{R}^n$. We construct an iterative algorithm in the Approximate Message Passing family which iterates over $A$ and its adjoint $A^*$, and establish a state evolution result which characterizes its behavior in the limit $d\rightarrow \infty, 2n/d^2 \rightarrow α$ in terms of a correlated Gaussian-semicircular process in a free probability space, in the sense of strong convergence of operators. We then apply this iteration to the random matrix discrepancy problem which asks for a binary vector $x \in \{-1,+1\}^n$ such that $A(x)$ has a small operator norm. Our algorithm achieves an operator norm $2σ(α)$, for an explicit expression of the standard deviation $σ(α)<1$ for all $0<α<α_* \simeq 5.74$. This resolves the algorithmic question of Kunisky-Zhang (2023) and Maillard (2025) in this interval.

Authors: August Y. Chen, Ahmed El Alaoui

Let $A_1,\ldots,A_n$ be independent $d \times d$ real symmetric Gaussian random matrices, and consider the linear operator $A(x) = n^{-1/2}\sum_{i=1}^n x_i A_i$, $x\in \mathbb{R}^n$. We construct an iterative algorithm in the Approximate Message Passing family which iterates over $A$ and its adjoint $A^*$, and establish a state evolution result which characterizes its behavior in the limit $d\rightarrow \infty, 2n/d^2 \rightarrow α$ in terms of a correlated Gaussian-semicircular process in a free probability space, in the sense of strong convergence of operators. We then apply this iteration to the random matrix discrepancy problem which asks for a binary vector $x \in \{-1,+1\}^n$ such that $A(x)$ has a small operator norm. Our algorithm achieves an operator norm $2σ(α)$, for an explicit expression of the standard deviation $σ(α)<1$ for all $0<α<α_* \simeq 5.74$. This resolves the algorithmic question of Kunisky-Zhang (2023) and Maillard (2025) in this interval.

Friday, September 11 2026, 00:00

Computing the Shortest Even Directed-Cycle Length in $\widetilde{O}(n^4)$ Time