STOC 2026
58th Annual ACM Symposium on Theory of Computing (STOC 2026)

Title Page


Article: stoc26foreword-fm000-p doi:

Welcome from the Chairs
The papers in this volume were presented at the 58th Annual ACM Symposium on Theory of Computing (STOC 2026), sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT). The conference was held in Salt Lake City, Utah, USA, June 22–27, 2026, with the papers being presented as live talks. STOC 2026 was part of TheoryFest, with an expanded program of STOC papers, poster sessions, and a broad cross-section of invited talks, workshops, tutorials, and social events. A special highlight this year is the 2026 Turing Award Lecture by Charles H. Bennett.

Article: stoc26foreword-fm001-p doi:

STOC 2026 Organization


Article: stoc26foreword-fm002-p doi:

STOC 2026 Sponsors


Article: stoc26foreword-fm003-p doi:

Lower Bounds against the Ideal Proof System in Finite Fields
Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, and Iddo Tzameret
(Imperial College London, UK)
Lower bounds against strong algebraic proof systems, and specifically fragments of the Ideal Proof System (IPS), have been obtained in an ongoing line of work. With the exception of the placeholder model, where the instance itself lacks small circuits, all existing bounds are proved only over large (or characteristic 0) fields, whereas finite fields form the more natural setting for propositional proof complexity. This work establishes lower bounds against fragments of IPS over constant-sized finite fields, resolving an open problem left by a series of prior works beginning with Forbes, Shpilka, Tzameret, and Wigderson (Theor. of Comput.’21), persisting with Behera, Limaye, Ramanathan, and Srinivasan (ICALP’25), and most recently posed by Forbes (CCC’24). We further highlight the importance of the constant-sized finite field regime in IPS by showing that any hard instance in this regime for a sufficiently strong proof system translates into a hard instance against AC⁰[p]-Frege, whose lower bounds remain a longstanding open problem.
Specifically, for constant-depth multilinear IPS, we prove that a variant of the knapsack instance studied by Govindasamy, Hakoniemi, and Tzameret (FOCS’22) has no polynomial-size IPS refutation over finite fields when the refutation is multilinear and written as a constant-depth circuit. Our argument has two key ingredients: (i) the recent set-multilinearization result of Forbes, which extends the earlier result of Limaye, Srinivasan, and Tavenas (J. ACM’25) to all fields; and (ii) an extension of the techniques of Govindasamy et al. to finite fields, obtained by constructing a new knapsack variant and generalizing the degree lower bound used in their work. This improves on Behera et al., who obtained related results for fragments of IPS over fields of positive characteristic. Their result requires the field size to grow with the instance, whereas ours does not. Hence, in the constant positive characteristic setting, our IPS lower bound subsumes theirs as it also holds over constant-sized finite fields. Moreover, we separate our proof system from that of Govindasamy et al. by constructing a further knapsack variant and proving a new degree lower bound.
We also present new lower bounds for read-once algebraic branching program refutations, roABP-IPS, in finite fields, extending results of Forbes et al. and Hakoniemi, Limaye, and Tzameret (STOC’24).
Finally, via an algebraic-to-CNF translation, we show that any lower bound against any proof system at least as strong as (non-multilinear) constant-depth IPS over finite fields for any instance, even a purely algebraic instance (i.e., not a translation of a Boolean formula or CNF), implies a hard CNF formula for the respective IPS fragment, and hence an AC⁰[p]-Frege lower bound by known simulations over finite fields (Grochow and Pitassi (J. ACM’18)).

@InProceedings{STOC26p1, author = {Tal Elbaz and Nashlen Govindasamy and Jiaqi Lu and Iddo Tzameret}, title = {Lower Bounds against the Ideal Proof System in Finite Fields}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1-12}, doi = {10.1145/3798129.3800721}, year = {2026}, } Publisher's Version Article: stoc26main-p4-p doi:10.1145/3798129.3800721

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
Jason Li
(Carnegie Mellon University, USA)
We obtain the first near-linear time deterministic algorithm for negative-weight single-source shortest paths on integer-weighted graphs. Our main ingredient is a deterministic construction of a padded decomposition on directed graphs, which may be of independent interest.

@InProceedings{STOC26p13, author = {Jason Li}, title = {Deterministic Padded Decompositions and Negative-Weight Shortest Paths}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {13-18}, doi = {10.1145/3798129.3800722}, year = {2026}, } Publisher's Version Article: stoc26main-p8-p doi:10.1145/3798129.3800722

Forbidden Subgraphs of Graphs with Low Bandwidth
Maria Chudnovsky, Daniel Lokshtanov, and Eran Nevo
(Princeton University, USA; University of California at Santa Barbara, USA; Hebrew University of Jerusalem, Israel; Universidad de Valladolid, Valladolid, Spain)
A layout of a graph G is an injective function f : V(G) → ℤ, and the bandwidth of a layout f is (G,f) = max_{uv ∈ E(G)} |f(u) − f(v)|. The bandwidth (G) of G is the minimum bandwidth of a layout of G. Computing the bandwidth of a graph is a notoriously hard problem: assuming P ≠ NP there is no polynomial time algorithm, even on very restricted classes of trees [Monien, SIAM Journal on Algebraic Discrete Methods, 1986], and no constant factor approximation, even on trees [Dubey et al., JCSS 2011]. Assuming the Exponential Time Hypothesis there is no algorithm with running time f(k)n^o(k) to determine whether an input graph has bandwidth at most k, even on very restricted classes of trees [Dregi and Lokshtanov, ICALP 2014].
In this paper we show that bandwidth of general graphs is FPT-approximable. In particular we give an algorithm that takes as input a graph G and integer k, runs in time f(k)n^O(1) for some function f, and either outputs a subtree T of G such that (T) ≥ k, or a layout f of G of bandwidth at most (10⁸⁴ · 4^{11 k} · k⁴)^4k. This resolves in the affirmative an open problem of Chung and Seymour [Discrete Mathematics, 1989], who asked whether the bandwidth of every graph G is upper bounded in terms of the maximum bandwidth of one of its subtrees. Our theorem leads to a forbidden subgraph characterization for graphs of bounded bandwidth, and can be seen as an analog for bandwidth of the classic grid minor theorem for treewidth, forbidden subtree theorem for pathwidth, and forbidden sub-path theorem for tree-depth.

@InProceedings{STOC26p19, author = {Maria Chudnovsky and Daniel Lokshtanov and Eran Nevo}, title = {Forbidden Subgraphs of Graphs with Low Bandwidth}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {19-30}, doi = {10.1145/3798129.3800723}, year = {2026}, } Publisher's Version Article: stoc26main-p21-p doi:10.1145/3798129.3800723

SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to Use the Simplicity of Cryptographic Reasoning)
Yao-Ching Hsieh, Abhishek Jain, Jiatu Li, and Surya Mathialagan
(University of Washington, USA; NTT Research, USA; Johns Hopkins University, USA; Massachusetts Institute of Technology, USA)
Modern cryptography relies on the intractability of computational problems. We present an approach to build cryptography from a new source of hardness: proving mathematical theorems. Unprovability results are abundant in mathematics and theoretical computer science, yet to our knowledge, they have not been used as a resource for cryptography.
Our main result is a construction of succinct non-interactive arguments (SNARGs) for NP under a new, but natural assumption on the hardness of proving lower bounds in the area of proof complexity. Specifically, our assumption states that it is impossible to prove, within a weak bounded arithmetic theory, the correctness of certifying hard tautologies against Extended Frege. This assumption is inspired by an informal mathematical challenge proposed by Razborov (2015), and can be viewed as a generalization of an unconditional unprovability result due to Krajíček and Pudlák (1989).
Our construction is, in fact, a simple variant of the SNARG constructed by Jin, Kalai, Lombardi, and Vaikuntanathan (2024). While the soundness of their construction was only proven for a subclass of NP, we prove its soundness for all NP under our assumption. At the heart of our result is the key observation that cryptographic reasoning is simple in a formal sense: the security proof of most cryptographic primitives can be formalized in a weak theory. In particular, we show how to formalize the scheme of Jin et al. in Jeřábek’s theory ₁ (2007) – a weak theory in bounded arithmetic.

@InProceedings{STOC26p31, author = {Yao-Ching Hsieh and Abhishek Jain and Jiatu Li and Surya Mathialagan}, title = {SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to Use the Simplicity of Cryptographic Reasoning)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {31-41}, doi = {10.1145/3798129.3800724}, year = {2026}, } Publisher's Version Article: stoc26main-p24-p doi:10.1145/3798129.3800724

Smoothed Analysis of Learning from Positive Samples
Jane H. Lee, Anay Mehrotra, and Manolis Zampetakis
(Yale University, USA; Stanford University, USA)
Binary classification from positive-only samples is a variant of PAC learning where the learner receives i.i.d. positively labeled samples and aims to learn a classifier that, with high probability, achieves low classification error. Previous work by Natarajan in STOC 1987 and Shvaytser in 1990 characterized learnability in this setting and revealed a largely negative picture: almost no interesting classes, including two-dimensional halfspaces, are learnablefrom positive-only examples. This poses significant challenges for the plethora of applications of positive-only learning from bioinformatics to ecology, where practitioners rely on heuristics for learning.
In this work, we initiate a smoothed analysis of positive-only learning. We assume we have access to samples from a reference distribution D such that the true data distribution D^⋆ is smooth with respect to it. Our first result demonstrates that, in stark contrast to the worst-case setting, all VC classes become learnable in the smoothed model, requiring O(VC/є²) positive samples to guarantee є-classification error. We then present a computationally efficient algorithm for any concept class that admits poly(є)-approximation by degree-k polynomials whose range is lower-bounded by a constant) with respect to D in the L₁-norm. The algorithm runs in time poly(d^k/є), which qualitatively matches the running time of the L1-regression algorithm. This smoothed analysis contributes to the growing body of work designing better learning guarantees under smoothness (Haghtalab et al. in J. ACM 2024, Chandrasekaran et al. in COLT 2024).
Our results also imply faster or more general algorithms for the following problems: (1) Estimation under unknown truncation, where we give the first polynomial sample and time algorithm for estimating the parameters of an exponential family distribution from samples truncated to an unknown set S^⋆ that is approximable by polynomials (whose range is lower-bounded by a constant) in L₁-norm. For many set-families, this improves upon Kontonis et al. in FOCS 2019 and Lee et al. in FOCS 2024, which required strong approximation with respect to L₂. (2) Truncation detection, where we present the first algorithm for detecting whether given samples have been truncated (or not) for a broad class of distributions, including non-product distributions. This improves upon De et al. in STOC 2024 who were limited to product distributions. (3) Learning with a list of reference distributions, as a corollary of our main result on smoothed analysis. We obtain analogous sample and computational complexity results in the more general setting where we do not have access to (samples from) a reference distribution D but rather only have access to samples from a list of O(1) distributions one of which witnesses the smoothness of D^⋆. This naturally arises if list-decoding algorithms are used to learn samplers for D^⋆ from corrupted data.

@InProceedings{STOC26p42, author = {Jane H. Lee and Anay Mehrotra and Manolis Zampetakis}, title = {Smoothed Analysis of Learning from Positive Samples}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {42-53}, doi = {10.1145/3798129.3800725}, year = {2026}, } Publisher's Version Article: stoc26main-p25-p doi:10.1145/3798129.3800725

Few Single-Qubit Measurements Suffice to Certify Any Quantum State
Meghal Gupta, William He, and Ryan O'Donnell
(University of California at Berkeley, USA; Carnegie Mellon University, USA)
A fundamental task in quantum information science is state certification: testing whether a lab-prepared n-qubit state is close to a given hypothesis state. In this work, we show that every pure hypothesis state can be certified using only O(n^2) single-qubit measurements applied to O(n) copies of the lab state. Prior to our work, it was not known whether even subexponentially many single-qubit measurements could suffice to certify arbitrary states. This resolves the main open question of Huang, Preskill, and Soleimanifar (FOCS 2024, QIP 2024).
Our algorithm also showcases the power of adaptive measurements: within each copy of the lab state, previous measurement outcomes dictate how subsequent qubit measurements are made. We show that the adaptivity is necessary, by proving an exponential lower bound on the number of copies needed for any nonadaptive single-qubit measurement algorithm.

@InProceedings{STOC26p54, author = {Meghal Gupta and William He and Ryan O'Donnell}, title = {Few Single-Qubit Measurements Suffice to Certify Any Quantum State}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {54-60}, doi = {10.1145/3798129.3800726}, year = {2026}, } Publisher's Version Article: stoc26main-p26-p doi:10.1145/3798129.3800726

Separator Theorem for Minor-Free Graphs in Linear Time
Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, and Tomáš Masařík
(CNRS - ENS de Lyon - Université Claude Bernard Lyon 1, France; University of Copenhagen, Denmark; University of Massachusetts at Amherst, USA; Carnegie Mellon University, USA; University of Warsaw, Poland)
The planar separator theorem by Lipton and Tarjan [FOCS ’77, SIAM Journal on Applied Mathematics ’79] states that any planar graph with n vertices has a balanced separator of size O(√n) that can be found in linear time. This landmark result kicked off decades of research on designing linear or nearly linear-time algorithms on planar graphs. In an attempt to generalize Lipton-Tarjan’s theorem to nonplanar graphs, Alon, Seymour, and Thomas [STOC ’90, Journal of the AMS ’90] showed that any minor-free graph admits a balanced separator of size O(√n) that can be found in O(n^3/2) time. The superlinear running time in their separator theorem is a key bottleneck for generalizing algorithmic results from planar to minor-free graphs. Despite extensive research for more than two decades, finding a balanced separator of size O(√n) in (linear) O(n) time for minor-free graphs has remained a major open problem. Known algorithms either give a separator of size much larger than O(√n) or have superlinear running time, or both.
In this paper, we answer the open problem affirmatively. Our algorithm is very simple: it runs a vertex-weighted variant of breadth-first search (BFS) a constant number of times on the input graph. Our key technical contribution is a weighting scheme on the vertices to guide the search for a balanced separator, offering a new connection between the size of a balanced separator and the existence of a clique-minor model. We believe that our weighting scheme may be of independent interest.

@InProceedings{STOC26p61, author = {Édouard Bonnet and Tuukka Korhonen and Hung Le and Jason Li and Tomáš Masařík}, title = {Separator Theorem for Minor-Free Graphs in Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {61-71}, doi = {10.1145/3798129.3800727}, year = {2026}, } Publisher's Version Article: stoc26main-p31-p doi:10.1145/3798129.3800727

Near Optimal Hardness of Approximating 𝑘-CSP
Dor Minzer and Kai Zhe Zheng
(Massachusetts Institute of Technology, USA)
We show that for every k∈ℕ and ε>0, for large enough alphabet R, given a k-CSP with alphabet size R, it is NP-hard to distinguish between the case that there is an assignment satisfying at least 1−ε fraction of the constraints, and the case no assignment satisfies more than 1/R^k−1−ε of the constraints. This result improves upon prior work of [Chan, Journal of the ACM 2016], who showed the same result with weaker soundness of O(k/R^k−2), and nearly matches the trivial approximation algorithm that finds an assignment satisfying at least 1/R^k−1 fraction of the constraints. Our proof follows the approach of a recent work [Minzer and Zheng, STOC 2024] of the authors, wherein the above result is proved for k=2. Our main new ingredient is a counting lemma for hyperedges between pseudo-random sets in the Grassmann graphs, which may be of independent interest.

@InProceedings{STOC26p72, author = {Dor Minzer and Kai Zhe Zheng}, title = {Near Optimal Hardness of Approximating 𝑘-CSP}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {72-83}, doi = {10.1145/3798129.3800728}, year = {2026}, } Publisher's Version Article: stoc26main-p34-p doi:10.1145/3798129.3800728

On the Learning Curves of Revenue Maximization
Steve Hanneke, Alkis Kalavasis, Shay Moran, and Grigoris Velegkas
(Purdue University, USA; Yale University, USA; Technion, Israel; Google Research, Israel; Google Research, USA)
Learning curves are a fundamental primitive in supervised learning, describing how an algorithm’s performance improves with more data and providing a quantitative measure of its generalization ability. Formally, a learning curve plots the decay of an algorithm’s error for a fixed underlying distribution as a function of the number of training samples. Prior work on revenue-maximizing learning algorithms, starting with the seminal work of Cole and Roughgarden, adopts a distribution-free perspective (which parallels the PAC learning framework in learning theory). This approach evaluates performance against the hardest possible sequence of valuation distributions, one for each sample size, effectively defining the upper envelope of learning curves over all possible distributions, thus leading to error bounds that do not capture the shape of the learning curves.
In this work we initiate the study of learning curves for revenue maximization and we provide a near-complete characterization of their rate of decay in the basic setting of a single item and a single buyer. In the absence of any restriction on the valuation distribution, we show that there exists a Bayes-consistent algorithm, meaning its learning curve converges to zero for any arbitrary valuation distribution as the number of samples n → ∞. However, this convergence must be arbitrarily slow, even if the optimal revenue is finite. In contrast, if the optimal revenue is achieved by a finite price then the optimal rate of decay is roughly 1/√n. Finally, for distributions supported on discrete sets of values, we show that learning curves decay (almost) exponentially fast, a rate unattainable under the PAC framework.
From a technical perspective, establishing lower bounds on learning curves is significantly more challenging than in the PAC framework, as it requires fixing a single hard distribution and proving a bound that holds for infinitely many values of n. Conversely, deriving upper bounds involves non-trivial algorithmic principles, including techniques such as regularization and structural risk minimization, which are crucial for achieving optimal learning rates.

@InProceedings{STOC26p84, author = {Steve Hanneke and Alkis Kalavasis and Shay Moran and Grigoris Velegkas}, title = {On the Learning Curves of Revenue Maximization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {84-92}, doi = {10.1145/3798129.3800729}, year = {2026}, } Publisher's Version Article: stoc26main-p38-p doi:10.1145/3798129.3800729

A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning Conjunctions
Xi Chen, Shyamal Patel, and Rocco A. Servedio
(Columbia University, USA)
The main conceptual contribution of this paper is identifying a previously unnoticed connection between two central problems in computational learning theory and property testing: agnostically learning conjunctions and tolerantly testing juntas. Inspired by this connection, the main technical contribution is a pair of improved algorithms for these two problems.
First we give a distribution-free algorithm for agnostically PAC learning conjunctions over {± 1}ⁿ that runs in time 2^Õ(n1/3), for constant excess error є. This improves on the fastest previously published algorithm, which runs in time 2^Õ(n1/2).
Building on the ideas in our agnostic conjunction learner and using significant additional technical ingredients, we give an adaptive tolerant testing algorithm for k-juntas (in the standard uniform-distribution property testing framework) with 2^Õ(k1/3) queries, for constant “gap parameter” є between the “near” and “far” cases. This improves on the best previous results, which make 2^Õ(√k) queries. Since there is a known 2^Ω(√k) lower bound for non-adaptive tolerant junta testers, our result shows that adaptive tolerant junta testing algorithms provably outperform non-adaptive ones.

@InProceedings{STOC26p93, author = {Xi Chen and Shyamal Patel and Rocco A. Servedio}, title = {A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning Conjunctions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {93-100}, doi = {10.1145/3798129.3800730}, year = {2026}, } Publisher's Version Article: stoc26main-p48-p doi:10.1145/3798129.3800730

No Exponential Quantum Speedup for SIS∞ Anymore
Robin Kothari, Ryan O'Donnell, and Kewen Wu
(Google Quantum AI, USA; Carnegie Mellon University, USA; Institute for Advanced Study at Princeton, USA)
In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case ℓ_∞-Short Integer Solution (SIS^∞) problem, in a parameter range outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. This was particularly exciting since SIS^∞ is a simple problem without structure, and their algorithmic techniques were different from those used in prior exponential quantum speedups.
We present efficient classical algorithms for all of the SIS^∞ and (more general) Constrained Integer Solution problems studied in their paper, showing there is no exponential quantum speedup anymore.

@InProceedings{STOC26p101, author = {Robin Kothari and Ryan O'Donnell and Kewen Wu}, title = {No Exponential Quantum Speedup for SIS∞ Anymore}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {101-105}, doi = {10.1145/3798129.3800731}, year = {2026}, } Publisher's Version Article: stoc26main-p52-p doi:10.1145/3798129.3800731

Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs
Ron Mosenzon
(Toyota Technological Institute at Chicago, USA)
We develop new (1+є)-approximation algorithms for finding the global minimum edge-cut in a directed edge-weighted graph, and for finding the global minimum vertex-cut in a directed vertex-weighted graph. Our algorithms are randomized, and have a running time of O(m^1+o(1)/є) on any m-edge n-vertex input graph, assuming all edge/vertex weights are polynomially-bounded. In particular, for any constant є>0, our algorithms have an almost-optimal running time of O(m^1+o(1)). The fastest previously-known running time for this setting, due to (Cen et al., FOCS 2021), is O(min{n²/є²,m^1+o(1)√n}) for Minimum Edge-Cut, and O(n²/є²) for Minimum Vertex-Cut.
Our results further extend to the rooted variants of the Minimum Edge-Cut and Minimum Vertex-Cut problems, where the algorithm is additionally given a root vertex r, and the goal is to find a minimum-weight cut separating any vertex from the root r.
In terms of techniques, we build upon and extend a framework that was recently introduced by (Chuzhoy et al., SODA 2026) for solving the Minimum Vertex-Cut problem in unweighted directed graphs. Additionally, in order to obtain our result for the Global Minimum Vertex-Cut problem, we develop a novel black-box reduction from this problem to its rooted variant. Prior to our work, such reductions were only known for more restricted settings, such as when all vertex-weights are unit.

@InProceedings{STOC26p106, author = {Ron Mosenzon}, title = {Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {106-117}, doi = {10.1145/3798129.3800732}, year = {2026}, } Publisher's Version Article: stoc26main-p53-p doi:10.1145/3798129.3800732

Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method
Yang P. Liu
(Carnegie Mellon University, USA)
We give an algorithm that takes a directed graph G undergoing m edge insertions with lengths in [1, W], and maintains (1+є)-approximate shortest path distances from a fixed source s to all other vertices. The algorithm is deterministic and runs in total time m^1+o(1)logW, for any є > exp(−(logm)^0.99). This is achieved by designing a nonstandard interior point method to crudely detect when the distances from s to other vertices v have decreased by a (1+є) factor, and implementing it using the deterministic min-ratio cycle data structure of [Chen-Kyng-Liu-Meierhans-Probst, STOC 2024].

@InProceedings{STOC26p118, author = {Yang P. Liu}, title = {Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {118-127}, doi = {10.1145/3798129.3800733}, year = {2026}, } Publisher's Version Info Article: stoc26main-p55-p doi:10.1145/3798129.3800733

S-Unit Equations in Modules and Linear-Exponential Diophantine Equations
Ruiwen Dong and Doron Shafrir
(University of Oxford, UK; Ben-Gurion University of the Negev, Israel)
Let T be a positive integer and M be a finitely presented module over the Laurent polynomial ring ℤ_/T[X₁^±, …, X_N^±]. We consider S-unit equations over M: these are equations of the form x₁ m₁ + ⋯ + x_K m_K = m₀, where the variables x₁, …, x_K range over the set of monomials (with coefficient 1) of ℤ_/T[X₁^±, …, X_N^±]. When T is a power of a prime number p, we show that the solution set of an S-unit equation over M is effectively p-normal in the sense of Derksen and Masser (2015). This generalizes their result on S-unit equations in fields of prime characteristic. When T is an arbitrary positive integer, we show that deciding whether an S-unit equation over M admits a solution is Turing equivalent to solving a system of linear-exponential Diophantine equations, whose base contains the prime divisors of T. Combined with a recent result of Karimov, Luca, Nieuwveld, Ouaknine and Worrell (2025), this yields decidability when T has at most two distinct prime divisors. This also shows that proving either decidability or undecidability in the case of arbitrary T would entail major breakthroughs in number theory. S-unit equations in modules have direct connections to many problems in computational algebra such as finding sparse polynomials in ideals, identifying zeros of linear recurrence sequences, and deciding membership problems in metabelian groups. In particular, a direct consequence of our result is the decidability Submonoid Membership in wreath products of the form ℤ_{/p^a q^b} ≀ ℤ^d.

@InProceedings{STOC26p128, author = {Ruiwen Dong and Doron Shafrir}, title = {S-Unit Equations in Modules and Linear-Exponential Diophantine Equations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {128-137}, doi = {10.1145/3798129.3800734}, year = {2026}, } Publisher's Version Article: stoc26main-p56-p doi:10.1145/3798129.3800734

The Weak Rank Principle: Lower Bounds and Applications
Michal Garlík, Svyatoslav Gryaznov, Hanlin Ren, and Iddo Tzameret
(Imperial College London, UK; Institute for Advanced Study at Princeton, USA)
Given two symbolic matrices X and Y of dimensions m × n and n × m, respectively, the rank principle states that when m = n+1 and A is a scalar matrix of rank n+1, the equation XY = A is unsatisfiable. When m is arbitrarily larger than n and A has rank exceeding n, we obtain the weak rank principle. We study this principle as an algebraic generalisation of the weak pigeonhole principle (WPHP), asserting that m pigeons cannot be injected into n holes, extending its counting argument to an algebraic setting. As a strengthening of WPHP, it admits proof complexity lower bounds in settings where none are known for WPHP, yet we show that these still yield applications analogous to those of WPHP. In particular, using new generalised types of random restrictions, which may be interesting by themselves, this allows us to resolve a number of open problems in proof complexity, including the construction of proof complexity generators for Polynomial Calculus Resolution over the two-element field (PCR_F2), new generators for Sherali–Adams (SA), and hardness results for circuit lower bound statements against PCR_F2, as detailed below.
Generators for PCR_F2. We prove exponential size lower bounds for several encodings—both algebraic and CNF—of the weak rank principle in PCR over F₂, where no such bounds are known for the WPHP in the regime with arbitrarily many pigeons. In particular, we obtain 2^Ω(n) size lower bounds for both algebraic and standard CNF encodings, including the bamboo-tree encoding, which is the most useful and corresponds to a circuit encoding, as considered by Alekhnovich, Ben-Sasson, Razborov, and Wigderson (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015). Our bounds hold for every matrix A in XY = A, implying that the rank principle forms a proof complexity generator with nearly quadratic stretch. Using a standard iteration technique we amplify the stretch to 2^nΩ(1), meaning we obtain a function generator. This resolves an open problem posed by Alekhnovich et al. (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015) concerning the construction of proof complexity generators with good stretch for PCR_F2.
Generators for SA. Since in SA even the strong pigeonhole principle is easy, we develop a new size lower-bound technique showing that the weak rank principle, encoded as a bamboo-tree CNF, serves as a proof complexity generator for SA. Our method introduces a new relaxed notion of degree and a new corresponding pseudoexpectation tailored specifically to the rank principle (and incompatible with the pigeonhole principle).
Circuit lower bound formulas. We show that PCR_F2 does not admit short proofs of lower-bound statements against Boolean circuits, nor against weak models of algebraic circuits such as non-commutative algebraic branching programs. This settles an open problem raised by Razborov (Ann. Math., 2015) concerning the provability of such lower bounds in PCR_F2.
Rank principle as an axiom. Finally, we demonstrate the centrality of the weak rank principle by showing that it is necessary for proving NC² circuit lower bounds and sufficient for proving AC⁰[p] lower bounds.

@InProceedings{STOC26p138, author = {Michal Garlík and Svyatoslav Gryaznov and Hanlin Ren and Iddo Tzameret}, title = {The Weak Rank Principle: Lower Bounds and Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {138-149}, doi = {10.1145/3798129.3800735}, year = {2026}, } Publisher's Version Article: stoc26main-p65-p doi:10.1145/3798129.3800735

Compressed Permutation Oracles
Joseph Carolan
(University of Maryland at College Park, USA)
The analysis of quantum algorithms which query random, invertible permutations has been a long-standing challenge in cryptography. Many techniques which apply to random oracles fail, or are not known to generalize to this setting. As a result, foundational cryptographic constructions involving permutations often lack quantum security proofs. With the aim of closing this gap, we develop and prove soundness of a compressed permutation oracle. Our construction shares many of the attractive features of Zhandry's original compressed function oracle: the purification is a small list of input-output pairs which meaningfully reflect an algorithm's knowledge of the oracle.
We then apply this framework to show that the Feistel construction with seven rounds is a strong quantum PRP, resolving an open question of (Zhandry, 2012). We further re-prove essentially all known quantum query lower bounds in the random permutation model, notably the collision and preimage resistance of both Sponge and Davies-Meyer, hardness of double-sided zero search and sparse predicate search, and give new lower bounds for cycle finding and the one-more problem.

@InProceedings{STOC26p150, author = {Joseph Carolan}, title = {Compressed Permutation Oracles}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {150-161}, doi = {10.1145/3798129.3800736}, year = {2026}, } Publisher's Version Article: stoc26main-p68-p doi:10.1145/3798129.3800736

Optimal Contest beyond Convexity
Negin Golrezaei, MohammadTaghi Hajiaghayi, and Suho Shin
(Massachusetts Institute of Technology, USA; University of Maryland, USA)
In the contest design problem, initiated by Lazear and Rosen (JPE’81), there are n strategic contestants, each of whom decides an effort level. A contest designer with a fixed budget must then design a mechanism that allocates a prize p_i to the i-th rank based on the outcome, to incentivize contestants to exert higher costly efforts and induce high-quality outcomes.
In this paper, we significantly deepen our understanding of optimal mechanisms in the complete information setting by considering nonconvex objective functions in contestants’ qualities. Notably, our results accommodate the following objective functions: (i) any convex combination of user welfare (motivated by recommender systems) and the average quality of contestants that is neither convex nor concave, (ii) arbitrary posynomials over quality. In particular, these subsume classic measures in mechanism design such as social welfare, order statistics, and (inverse) S-shaped functions, which have received little or no attention in the contest literature to the best of our knowledge.
Surprisingly, across all these regimes, we show that the optimal mechanism is highly structured: it allocates potentially higher prize to the first-ranked contestant, zero to the last-ranked one, and equal prizes to the all intermediate contestants, p₁ ≥ p₂ = … = p_n−1 ≥ p_n = 0. In some special cases, we observe a stark phase transition between two extreme mechanisms: (i) policy (p₁ = 1, p₂ = … = p_n = 0) and (ii) policy (p₁ = … = p_n−1=1/(n−1), p_n = 0) depending on the objective and cost function, cementing and unifying evidences witnessed in the literature. More importantly, thanks to the structural characterization, we obtain a fully polynomial-time approximation scheme given a value oracle.
Our technical results rely on Schur-convexity (or concavity) of Bernstein basis polynomial–weighted functions, total positivity and variation diminishing property. En route to our results, we obtain a surprising reduction from a structured high-dimensional nonconvex optimization to a single-dimensional optimization by connecting the shape of the gradient sequences of the objective function to the number of transition points in optimum, which might be of independent interest.

@InProceedings{STOC26p162, author = {Negin Golrezaei and MohammadTaghi Hajiaghayi and Suho Shin}, title = {Optimal Contest beyond Convexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {162-173}, doi = {10.1145/3798129.3800737}, year = {2026}, } Publisher's Version Article: stoc26main-p69-p doi:10.1145/3798129.3800737

Closure under Factorization from a Result of Furstenberg
Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf
(University of Toronto, Canada; Tata Institute of Fundamental Research, Mumbai, India)
We show that algebraic formulas and constant-depth circuits are closed under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas respectively.
Our result turns out to be an elementary consequence of a fundamental and surprising result of Furstenberg from the 1960s, which gives a non-iterative description of the power series roots of a bivariate polynomial. Combined with standard structural ideas in algebraic complexity, we observe that this theorem yields the desired closure results.
As applications, we get alternative (and perhaps simpler) proofs of various known results and strengthen the quantitative bounds in some of them. This includes a unified proof of known closure results for algebraic models (circuits, branching programs and VNP), an extension of the analysis of the Kabanets-Impagliazzo hitting set generator to formulas and constant-depth circuits, and a (significantly) simpler proof of correctness as well as stronger guarantees on the output in the subexponential time deterministic algorithm for factorization of constant-depth circuits from a recent work of Bhattacharjee, Kumar, Ramanathan, Saptharishi & Saraf.

@InProceedings{STOC26p174, author = {Somnath Bhattacharjee and Mrinal Kumar and Shanthanu S. Rai and Varun Ramanathan and Ramprasad Saptharishi and Shubhangi Saraf}, title = {Closure under Factorization from a Result of Furstenberg}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {174-185}, doi = {10.1145/3798129.3800738}, year = {2026}, } Publisher's Version Article: stoc26main-p81-p doi:10.1145/3798129.3800738

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
Sumegha Garg, Jabari Hastings, Chirag Pabbaraju, and Vatsal Sharan
(Rutgers University, USA; Stanford University, USA; University of Southern California, USA)
We present a unified framework for proving memory lower bounds for multi‐pass streaming algorithms that detect planted structures. Planted structures — such as cliques or bicliques in graphs, and sparse signals in high-dimensional data — arise in numerous applications, and our framework yields multi-pass memory lower bounds for many such fundamental settings. We show memory lower bounds for the planted k-biclique detection problem in random bipartite graphs and for detecting sparse Gaussian means. We also show the first memory-sample tradeoffs for the sparse principal component analysis (PCA) problem in the spiked covariance model. For all these problems to which we apply our unified framework, we obtain bounds which are nearly tight in the low, O(logn) memory regime. We also leverage our bounds to establish new multi-pass streaming lower bounds, in the vertex arrival model, for two well-studied graph streaming problems: approximating the size of the largest biclique and approximating the maximum density of bounded-size subgraphs.
To show these bounds, we study a general distinguishing problem over matrices, where the goal is to distinguish a null distribution from one that plants an outlier distribution over a random submatrix. Our analysis builds on a new distributed data processing inequality that provides sufficient conditions for memory hardness in terms of the likelihood ratio between the averaged planted and null distributions. This result generalizes the inequality of [Braverman et al., STOC 2016] and may be of independent interest. The inequality enables us to measure information cost under the null distribution – a key step for applying subsequent direct-sum-type arguments and incorporating the multi-pass information cost framework of [Braverman et al., STOC 2024]. Finally, to instantiate our framework in concrete settings, we derive bounds on the likelihood ratio between the planted and null distributions using careful truncations.

@InProceedings{STOC26p186, author = {Sumegha Garg and Jabari Hastings and Chirag Pabbaraju and Vatsal Sharan}, title = {A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {186-197}, doi = {10.1145/3798129.3800739}, year = {2026}, } Publisher's Version Article: stoc26main-p85-p doi:10.1145/3798129.3800739

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
Bernhard Haeupler, Yonggang Jiang, and Thatchaphol Saranurak
(INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; MPI-INF, Germany; Saarland University, Germany; University of Michigan, USA)
We present the first deterministic nearly-linear time algorithm for single-source shortest paths with negative edge weights on directed graphs: given a directed graph G with n vertices, m edges whose weights are integer in {−W,…,W}, our algorithm either computes all distances from a source s or reports a negative cycle in time O(m)· log(nW) time.
All known near-linear time algorithms for this problem have been inherently randomized, as they crucially rely on low-diameter decompositions.
To overcome this barrier, we introduce a new structural primitive for directed graphs called the path cover. This plays a role analogous to neighborhood covers in undirected graphs, which have long been central to derandomizing algorithms that use low-diameter decomposition in the undirected setting. We believe that path covers will serve as a fundamental tool for the design of future deterministic algorithms on directed graphs.

@InProceedings{STOC26p198, author = {Bernhard Haeupler and Yonggang Jiang and Thatchaphol Saranurak}, title = {Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {198-209}, doi = {10.1145/3798129.3800740}, year = {2026}, } Publisher's Version Article: stoc26main-p87-p doi:10.1145/3798129.3800740

Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
Andrej Bogdanov, Alon Rosen, Neekon Vafa, and Vinod Vaikuntanathan
(University of Ottawa, Canada; Bocconi University, Italy; Massachusetts Institute of Technology, USA)
Johnson and Lindenstrauss (Contemporary Mathematics, 1984) showed that for n > m, a scaled random projection A from ℝⁿ to ℝ^m is an approximate isometry on any set S of size at most exponential in m. If S is larger, however, its points can contract arbitrarily under A. In particular, the hypergrid ([−B, B] ∩ ℤ)ⁿ is expected to contain a point that is contracted by a factor of κ_stat = Θ(B)^−1/α, where α = m/n.
We give evidence that finding such a point exhibits a statistical-computational gap precisely up to κ_comp = Θ(√α/B). On the algorithmic side, we design an online algorithm achieving κ_comp, inspired by a discrepancy minimization algorithm of Bansal and Spencer (Random Structures & Algorithms, 2020). On the hardness side, we show evidence via a multiple overlap gap property (mOGP), which in particular captures online algorithms; and a reduction-based lower bound, which shows hardness under standard worst-case lattice assumptions.
As a cryptographic application, we show that the rounded Johnson-Lindenstrauss embedding is a robust property-preserving hash function (Boyle, Lavigne and Vaikuntanathan, TCC 2019) on the hypergrid for the Euclidean metric in the computationally hard regime. Such hash functions compress data while preserving ℓ₂ distances between inputs up to some distortion factor, with the guarantee that even knowing the hash function, no computationally bounded adversary can find any pair of points that violates the distortion bound.

@InProceedings{STOC26p210, author = {Andrej Bogdanov and Alon Rosen and Neekon Vafa and Vinod Vaikuntanathan}, title = {Adaptive Robustness of Hypergrid Johnson-Lindenstrauss}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {210-221}, doi = {10.1145/3798129.3800741}, year = {2026}, } Publisher's Version Article: stoc26main-p98-p doi:10.1145/3798129.3800741

Beyond Smoothed Analysis: Analyzing the Simplex Method By-the-Book
Eleon Bach, Alexander E. Black, Sophie Huiberts, and Sean Kafer
(TU Munich, Germany; Bowdoin College, USA; LIMOS - CNRS - University Clermont Auvergne, France; Illinois State University, USA)
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new algorithm analysis framework that we call by-the-book analysis. In contrast to earlier frameworks, by-the-book analysis not only models an algorithm's input data, but also the algorithm itself. Results from by-the-book analysis are meant to correspond well with established knowledge of an algorithm's practical behavior, as they are meant to be grounded in observations from implementations, input modeling best practices, and measurements on practical benchmark instances. We apply our framework to the simplex method, an algorithm which is beloved for its excellent performance in practice and notorious for its high running time under worst-case analysis. The simplex method similarly showcased the previous state of the art framework smoothed analysis (Spielman and Teng, STOC'01). We explain how our framework overcomes several weaknesses of smoothed analysis and we prove that under input scaling assumptions, feasibility tolerances and other design principles used by simplex method implementations, the simplex method indeed attains a polynomial running time. Our results provide analytical justification for these features which are common to all high-quality simplex method implementations.

@InProceedings{STOC26p222, author = {Eleon Bach and Alexander E. Black and Sophie Huiberts and Sean Kafer}, title = {Beyond Smoothed Analysis: Analyzing the Simplex Method By-the-Book}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {222-233}, doi = {10.1145/3798129.3800742}, year = {2026}, } Publisher's Version Article: stoc26main-p103-p doi:10.1145/3798129.3800742

Sampling Permutations with Cell Probes Is Hard
Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, and Dmitry Sokolov
(Technion, Israel; EPFL, Switzerland; Université de Montréal, Canada)
Suppose we are given an infinite sequence of input cells, each initialized with a uniform random symbol from [n]. How hard is it to output a sequence in [n]ⁿ that is close to a uniform random permutation? Viola (SICOMP 2020) conjectured that if each output cell is computed by making d probes to input cells, then d≥ω(1). Our main result shows that, in fact, d≥ (logn)^Ω(1), which is tight up to the constant in the exponent. Our techniques also show that if the probes are nonadaptive, then d≥ n^Ω(1), which is an exponential improvement over the previous nonadaptive lower bound due to Yu and Zhan (ITCS 2024). Our results also imply lower bounds against succinct data structures for storing permutations.

@InProceedings{STOC26p234, author = {Yaroslav Alekseev and Mika Göös and Konstantin Myasnikov and Artur Riazanov and Dmitry Sokolov}, title = {Sampling Permutations with Cell Probes Is Hard}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {234-245}, doi = {10.1145/3798129.3800743}, year = {2026}, } Publisher's Version Article: stoc26main-p108-p doi:10.1145/3798129.3800743

A Dichotomy Theorem for Multi-pass Streaming CSPs
Yumou Fei, Dor Minzer, and Shuo Wang
(Massachusetts Institute of Technology, USA)
In a constraint satisfaction problem (CSP) in the single-pass streaming model, an algorithm is given the constraints C₁,…,C_m of an instance one after another (in some fixed order), and its goal is to approximate the value of the instance, i.e., the maximum fraction of constraints that can be satisfied simultaneously. In the p-pass streaming model the algorithm is given p passes over the input stream (in the same order), after which it is required to output an approximation of the value of the instance. We show a dichotomy result for p-pass streaming algorithms for all CSPs and for up to polynomially many passes. More precisely, we prove that for any arity parameter k, finite alphabet Σ, collection F of k-ary predicates over Σ and any c∈ (0,1), there exists 0<s≤ c such that:
(1) For any ε>0 there is a constant pass, O_ε(logn)-space randomized streaming algorithm solving cs−ε. That is, the algorithm accepts inputs with value at least c with probability at least 2/3, and rejects inputs with value at most s−ε with probability at least 2/3;
(2) for all ε>0, any p-pass (even randomized) streaming algorithm that solves the promise problem MaxCSP(F)[c,s+ε] must use Ω_ε(n^1/3/p) space.
Our algorithm is based on a certain linear-programming relaxation of the CSP and on a distributed algorithm that approximates its value. This part builds on the works [Yoshida, STOC 2011] and [Saxena, Singer, Sudan, Velusamy, SODA 2025]. For our hardness result we show how to translate an integrality gap of the linear program into a family of hard instances, which we then analyze via studying a related communication complexity problem. That analysis is based on discrete Fourier analysis and builds on a prior work of the authors and on the work [Chou, Golovnev, Sudan, Velusamy, J.ACM 2024].

@InProceedings{STOC26p246, author = {Yumou Fei and Dor Minzer and Shuo Wang}, title = {A Dichotomy Theorem for Multi-pass Streaming CSPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {246-255}, doi = {10.1145/3798129.3800744}, year = {2026}, } Publisher's Version Article: stoc26main-p111-p doi:10.1145/3798129.3800744

NP-Membership for the Boundary-Boundary Art-Gallery Problem
Jack Stade
(University of Copenhagen, Denmark)
The boundary-boundary art-gallery problem asks, given a polygon P representing an art-gallery, for a minimal set of guards that can see the entire boundary of P (the wall of the art gallery), where the guards must be placed on the boundary. That is, for each point on the boundary, there should be a line segment connecting it to one of the guards that is contained in P. We show that this art-gallery variant is in NP, even if the polygon can have holes. In order to prove this, we develop a constraint-propagation procedure for continuous constraint satisfaction problems where each constraint involves at most 2 variables.
The X-Y variant of the art-gallery problem is the one where the guards must lie in X and need to see all of Y. Each of X and Y can be either the vertices of the polygon, the boundary of the polygon, or the entire polygon, giving 9 different variants. Previously, it was known that X-vertex and vertex-Y variants are all NP-complete and that the point-point, point-boundary, and boundary-point variants are ∃ ℝ-complete [Abrahamsen, Adamaszek, and Miltzow, JACM 2021][Stade, SoCG 2025]. However, the boundary-boundary variant was only known to lie somewhere between NP and ∃ ℝ.
The X-vertex and vertex-Y variants can be straightforwardly reduced to discrete set-cover instances. In the full version, we give example to show that a solution to an instance of the boundary-boundary art-gallery problem sometimes requires placing guards at irrational coordinates, so it unlikely that the problem can be easily discretized.

@InProceedings{STOC26p256, author = {Jack Stade}, title = {NP-Membership for the Boundary-Boundary Art-Gallery Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {256-267}, doi = {10.1145/3798129.3800745}, year = {2026}, } Publisher's Version Article: stoc26main-p120-p doi:10.1145/3798129.3800745

Shortcutting for Negative-Weight Shortest Paths
George Z. Li, Jason Li, Satish Rao, and Junkai Zhang
(Carnegie Mellon University, USA; University of California at Berkeley, USA; Tsinghua University, China)
Consider the single-source shortest paths problem on a directed graph with real-valued edge weights. We solve this problem in O(n^2.5log^4.5n) time, improving on prior work of Fineman (STOC 2024) and Huang-Jin-Quanrud (SODA 2025, 2026) on dense graphs. Our main technique is a shortcutting procedure that iteratively reduces the number of negative-weight edges along shortest paths by a constant factor.

@InProceedings{STOC26p268, author = {George Z. Li and Jason Li and Satish Rao and Junkai Zhang}, title = {Shortcutting for Negative-Weight Shortest Paths}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {268-275}, doi = {10.1145/3798129.3800746}, year = {2026}, } Publisher's Version Article: stoc26main-p125-p doi:10.1145/3798129.3800746

Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
Fedor V. Fomin, Petr A. Golovach, Nikola Jedličková, Jan Kratochvíl, Danil Sagunov, and Kirill Simonov
(University of Bergen, Norway; Charles University, Czech Republic; Saint Petersburg State University, Russian Federation; V.A.Steklov Mathematical Institute of the Russian Academy of Sciences, Russian Federation)
The classic theorem of Gallai and Milgram (1960) generalizes several fundamental results in Graph Theory, such as Dilworth’s theorem on posets and Kőnig’s theorem on matchings in bipartite graphs. The theorem asserts that for every graph G, the vertex set of G can be partitioned into at most α(G) vertex-disjoint paths, where α(G) is the maximum size of an independent set in G. The proof of the Gallai-Milgram theorem is constructive and yields a polynomial-time algorithm that computes a covering of G by at most α(G) vertex-disjoint paths. While the Gallai-Milgram theorem is tight—there are graphs where one really needs α(G) paths, not fewer, to cover the vertex set of G—it was not known prior to our work whether deciding if a graph G could be covered by fewer than α(G) vertex-disjoint paths can be done in polynomial time. We resolve this question by proving the following algorithmic extension of the Gallai–Milgram theorem for undirected graphs: There is an algorithm that, for an n-vertex graph G and an integer parameter k ≥ 1, runs in time 2^2O(k4logk) · n^O(1) and outputs a path cover P of G together with either a correct conclusion that P is a minimum-size path cover or an independent set of size |P| + k, certifying that P contains at most α(G) − k paths. Thus, for k ∈ O((loglogn)^1/4−ε) our algorithm runs in polynomial time, and either computes a minimum-size path cover of G, or finds a path cover of size at most α(G) − k. We find the existence of such an algorithm quite surprising for the following reason. The problems of computing a path cover and a maximum independent set are both notoriously hard, yet our algorithm either solves one of them or provides meaningful information about the other. The proof of our algorithmic extension of the Gallai–Milgram theorem is non-trivial and builds on several novel algorithmic ideas. One of the key subroutines in our algorithm is an FPT algorithm, parameterized by α(G), for deciding whether G contains a Hamiltonian path. This result is of independent interest—prior to our work, no polynomial-time algorithm for deciding Hamiltonicity was known, even for graphs with independence number at most three. Moreover, the algorithmic techniques we develop apply to a wide array of problems in undirected graphs, including Hamiltonian Cycle, Path Cover, Largest Linkage, and Topological Minor Containment. We show that all these problems are FPT when parameterized by the independence number of the graph. Notably, the independence-number parameterization departs from the typical direction of research in parameterized complexity. First, α(G) measures a graph’s density, whereas most prior work in the area focuses on parameters describing sparsity, such as treewidth or vertex cover. Second, most structural parameters studied in parameterized complexity can be computed exactly or well-approximated in polynomial or even FPT time, whereas computing α(G) is notoriously difficult from almost any computational perspective. The fact that it can nevertheless serve as the basis for efficient parameterization is particularly striking.

@InProceedings{STOC26p276, author = {Fedor V. Fomin and Petr A. Golovach and Nikola Jedličková and Jan Kratochvíl and Danil Sagunov and Kirill Simonov}, title = {Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {276-285}, doi = {10.1145/3798129.3800747}, year = {2026}, } Publisher's Version Article: stoc26main-p127-p doi:10.1145/3798129.3800747

Fisher Meets Lindahl: A Unified Duality Framework for Market Equilibrium
Yixin Tao and Weiqiang Zheng
(Shanghai University of Finance and Economics, China; Yale University, USA)
The Fisher market equilibrium for private goods markets and the Lindahl equilibrium for public goods markets are classic and fundamental solution concepts for market equilibrium. While the Fisher market equilibrium has been well-studied, the theoretical foundations for the Lindahl equilibrium—including characterizations, computation, and dynamics—remain substantially underdeveloped.
In this work, we propose a unified duality framework for market equilibria in private goods and public goods markets. We show that every Lindahl equilibrium of a public goods market corresponds to a Fisher market equilibrium in a dual private goods market with dual utilities, and vice versa. The dual utility is based on the indirect utility, and the correspondence between the two equilibria works by exchanging the roles of allocations and prices. This duality framework enables us to transfer insights and results between the two settings. The framework also extends to markets with chores.
Using the duality framework, we address the gaps concerning the computation and dynamics for the Lindahl equilibrium and obtain new insights and developments for the Fisher market equilibrium. First, we leverage this duality to analyze welfare properties of Lindahl equilibria. For concave homogeneous utilities, we prove that a Lindahl equilibrium maximizes Nash Social Welfare (NSW). For concave non-homogeneous utilities, we show that a Lindahl equilibrium achieves (1/e)^1/e approximation to the optimal NSW, and the approximation ratio is tight. Second, we apply the duality framework to market dynamics, including proportional response dynamics (PRD) and tâtonnement. We obtain new market dynamics for the Lindahl equilibria from market dynamics in the dual Fisher market, significantly extending existing results for linear utilities. Moreover, the duality framework also introduces new insights into market dynamics. We show that the recently proposed PRD in gross substitutes Fisher markets is a best-response expenditure procedure in the dual Lindahl setting. Using this observation, we extend PRD to markets with total complements utilities, the dual class of gross substitutes utilities. Finally, we apply the duality framework to markets with chores. We propose a program for private chores for general convex homogeneous disutilities that avoids the “poles” issue, and every KKT point of the program corresponds to a Fisher market equilibrium. We also initiate the study of the Lindahl equilibrium for public chores using duality to the private chores setting.

@InProceedings{STOC26p286, author = {Yixin Tao and Weiqiang Zheng}, title = {Fisher Meets Lindahl: A Unified Duality Framework for Market Equilibrium}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {286-297}, doi = {10.1145/3798129.3800748}, year = {2026}, } Publisher's Version Article: stoc26main-p138-p doi:10.1145/3798129.3800748

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
Amey Bhangale, Mark Braverman, Subhash Khot, Yang Liu, Dor Minzer, and Kunal Mittal
(University of California at Riverside, USA; Princeton University, USA; New York University, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA)
Let G be a k-player game with value <1, whose query distribution is such that no marginal on k-1 players admits a non-trivial Abelian embedding. We show that for every n>=N, the value of the n-fold parallel repetition of G is val(G^n) <= 1/(log log ... log n), where the number of logarithms is C, and N=N(G) and 1 <= C <= k^(O(k)) are constants. As a consequence, we obtain a parallel repetition theorem for all 3-player games whose query distribution is pairwise-connected. Prior to our work, only inverse Ackermann decay bounds were known for such games.
As additional special cases, we obtain a unified proof for all known parallel repetition theorems, albeit with weaker bounds: (1) A new analytic proof of parallel repetition for all 2-player games. (2) A new proof of parallel repetition for all k-player playerwise connected games. (3) Parallel repetition for all 3-player games (in particular 3-XOR games) whose query distribution has no non-trivial Abelian embedding into (Z, +). (4) Parallel repetition for all 3-player games with binary inputs.

@InProceedings{STOC26p298, author = {Amey Bhangale and Mark Braverman and Subhash Khot and Yang Liu and Dor Minzer and Kunal Mittal}, title = {An Analytical Approach to Parallel Repetition via CSP Inverse Theorems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {298-304}, doi = {10.1145/3798129.3800749}, year = {2026}, } Publisher's Version Article: stoc26main-p148-p doi:10.1145/3798129.3800749

Fourier Spectrum of Noisy Quantum Algorithms
Uma Girish
(Columbia University, USA; University of Toronto, Canada)
Quantum computing promises exponential speedups for certain problems, yet fully universal quantum computers remain out of reach and near-term devices are inherently noisy. Motivated by this, we study noisy quantum algorithms and the landscape between BQP and BPP. We build on a powerful technique to differentiate quantum and classical algorithms called the level-ℓ Fourier growth (the sum of absolute values of Fourier coefficients of sets of size ℓ) and show that it can also be used to differentiate quantum algorithms based on the types of resources used. We show that noise acting on a quantum algorithm dampens its Fourier growth in ways intricately linked to the type of noise.
Concretely, we study noisy models of quantum computation where highly mixed states are prevalent, namely: DQCk algorithms, where k qubits are clean and the rest are maximally mixed, and 1/2-BQP algorithms, where the initial state is maximally mixed, but the algorithm is given knowledge of the initial state at the end of the computation. We establish upper bounds on the Fourier growth of DQCk, 1/2-BQP and BQP algorithms and leverage the differences between these bounds to derive oracle separations between these models. In particular, we show that 2-Forrelation and 3-Forrelation require N^Ω(1) queries in the DQC1 and 1/2-BQP models respectively. Our results are proved using a new matrix decomposition lemma that might be of independent interest.

@InProceedings{STOC26p305, author = {Uma Girish}, title = {Fourier Spectrum of Noisy Quantum Algorithms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {305-313}, doi = {10.1145/3798129.3800750}, year = {2026}, } Publisher's Version Info Article: stoc26main-p157-p doi:10.1145/3798129.3800750

MIPᶜᵒ=coRE
Junqiao (Randy) Lin
(CWI, Netherlands; QuSoft, Netherlands)
In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen shows that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP*, except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084].
We introduce a new equivalence condition for RE/coRE-complete problems, which we call the weakly compressible condition. We show that both MIP* and MIPco satisfy this condition through the compression theorem, and thereby establish that the uncomputability for MIP* and MIPco can be proved under a unified framework (despite these two complexity classes being different). Notably, this approach also gives an alternative proof of the MIP*=RE theorem, which does not rely on the preservation of the entanglement bound. In addition to non-local games, this new condition could also potentially be applicable to other promise problems.

@InProceedings{STOC26p314, author = {Junqiao (Randy) Lin}, title = {MIPᶜᵒ=coRE}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {314-322}, doi = {10.1145/3798129.3800751}, year = {2026}, } Publisher's Version Article: stoc26main-p163-p doi:10.1145/3798129.3800751

The Skolem Problem in Rings of Positive Characteristic
Ruiwen Dong and Doron Shafrir
(University of Oxford, UK; Ben-Gurion University of the Negev, Israel)
We show that the Skolem Problem is decidable in finitely generated commutative rings of positive characteristic. More precisely, we show that there exists an algorithm which, given a finite presentation of a (unitary) commutative ring R = ℤ_/T[X₁, …, X_n]/I of characteristic T > 0, and a linear recurrence sequence (γ_n)_{n ∈ ℕ} ∈ R^ℕ, determines whether (γ_n)_{n ∈ ℕ} contains a zero term. Our proof is based on two recent results: Dong and Shafrir (2026) on the solution set of S-unit equations over p^e-torsion modules, and Karimov, Luca, Nieuwveld, Ouaknine, and Worrell (2025) on solving linear equations over powers of two multiplicatively independent numbers. Our result implies, moreover, that the zero set of a linear recurrence sequence over a ring of characteristic T = p₁^e₁ ⋯ p_k^e_k is effectively a finite union of p_i-normal sets in the sense of Derksen (2007).

@InProceedings{STOC26p323, author = {Ruiwen Dong and Doron Shafrir}, title = {The Skolem Problem in Rings of Positive Characteristic}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {323-329}, doi = {10.1145/3798129.3800752}, year = {2026}, } Publisher's Version Article: stoc26main-p169-p doi:10.1145/3798129.3800752

Fine-Grained Complexity of Continuous Euclidean 𝑘-Center
Lotte Blank, Karl Bringmann, Parinya Chalermsook, Karthik C. S., Benedikt Kolbe, Hung Le, and Geert van Wordragen
(University of Bonn, Germany; ETH Zurich, Switzerland; University of Sheffield, UK; Rutgers University, USA; University of Massachusetts at Amherst, USA; Aalto University, Finland)
In the (continuous) Euclidean k-center problem, given n points in ℝ^d and an integer k, the goal is to find k center points in ℝ^d that minimize the maximum Euclidean distance from any input point to its closest center. In this paper, we establish conditional lower bounds for this problem in constant dimensions in two settings.
Parameterized by k: Assuming the Exponential Time Hypothesis (ETH), we show that there is no f(k)n^o(k1−1/d)-time algorithm for the Euclidean k-center problem. This result shows that the algorithm of Agarwal and Procopiuc [SODA 1998; Algorithmica 2002] is essentially optimal. Furthermore, our lower bound rules out any (1+ε)-approximation algorithm running in time (k/ε)^o(k1−1/d)n^O(1), thereby establishing near-optimality of the corresponding approximation scheme by the same authors.
Small k: Assuming the 3-SUM hypothesis, we prove that for any ε>0 there is no O(n^2−ε)-time algorithm for the Euclidean 2-center problem in ℝ³. This settles an open question posed by Agarwal, Ben Avraham, and Sharir [SoCG 2010; Computational Geometry 2013]. In addition, under the same hypothesis, we prove that for any ε > 0, the Euclidean 6-center problem in ℝ² also admits no O(n^2−ε)-time algorithm.
The technical core of all our proofs is a novel geometric embedding of a system of linear equations. We construct a point set where each variable corresponds to a specific collection of points, and the geometric structure ensures that a small-radius clustering is possible if and only if the system has a valid solution.

@InProceedings{STOC26p330, author = {Lotte Blank and Karl Bringmann and Parinya Chalermsook and Karthik C. S. and Benedikt Kolbe and Hung Le and Geert van Wordragen}, title = {Fine-Grained Complexity of Continuous Euclidean 𝑘-Center}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {330-341}, doi = {10.1145/3798129.3800753}, year = {2026}, } Publisher's Version Article: stoc26main-p171-p doi:10.1145/3798129.3800753

Generalized Samorodnitsky Noisy Function Inequalities, with Applications to Error-Correcting Codes
Olakunle Sunday Abawonse, Jan Hązła, and Ryan O'Donnell
(AIMS, Rwanda; Carnegie Mellon University, USA)
An inequality by Samorodnitsky states that if f:F₂ⁿ → ℝ is a nonnegative function, and S ⊆ [n] is chosen by randomly including each coordinate with probability a certain λ = λ(q,ρ) < 1, then log||T_ρf||_q ≤ E_S log||E(f|S)||_q. Samorodnitsky’s inequality has several applications to the theory of error-correcting codes. Perhaps most notably, it can be used to show that any binary linear code (with minimum distance ω(logn)) that has vanishing decoding error probability on the BEC(λ) (binary erasure channel) also has vanishing decoding error on all memoryless symmetric channels with capacity above some C = C(λ).
Samorodnitsky determined the optimal λ = λ(q,ρ) for his inequality in the case that q ≥ 2 is an integer. In this work, we generalize the inequality to f : Ωⁿ → ℝ under any product probability distribution µ^{⊗ n} on Ωⁿ; moreover, we determine the optimal value of λ = λ(q,µ,ρ) for any real q ∈ [2,∞], ρ ∈ [0,1], and distribution µ. As one consequence, we obtain the analogue of the aforementioned coding theory result for linear codes over any finite alphabet.

@InProceedings{STOC26p342, author = {Olakunle Sunday Abawonse and Jan Hązła and Ryan O'Donnell}, title = {Generalized Samorodnitsky Noisy Function Inequalities, with Applications to Error-Correcting Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {342-353}, doi = {10.1145/3798129.3800754}, year = {2026}, } Publisher's Version Article: stoc26main-p175-p doi:10.1145/3798129.3800754

A Sharp Characterization of Pessiland
Shuichi Hirahara and Mikito Nanashima
(National Institute of Informatics, Tokyo, Japan; Institute of Science Tokyo, Japan)
It is a long-standing open question whether the average-case hardness of NP implies the existence of a one-way function. The hypothetical world in which this does not hold is called Pessiland, which is the most pessimistic among Impagliazzo’s five possible worlds. In this paper, we present the first ”sharp” characterization of Pessiland: (i) NP is hard on average if and only if the minimum description length of programs in agnostic learning is hard to approximate on average with an approximation factor ℓ / polylog(ℓ), where ℓ is a new complexity measure of a distribution called advice complexity of sampling; and (ii) a one-way function does not exist if and only if the minimum description length of programs in agnostic learning is easy to approximate on average with an approximation factor O(ℓ). In particular, Pessiland is ruled out if and only if the small quantitative gap in approximation factors ℓ/polylog(ℓ) and O(ℓ) is closed.
Our characterization is based on an optimal NP-hardness result for the Collective Minimum Monotone Satisfying Assignment (CMMSA) Problem, whose task is, given as input a collection of monotone formulas with at most ℓ literals, to compute the minimum weight of an assignment that satisfies as many monotone formulas as possible. We prove the NP-hardness of approximating the minimum weight within a factor of ℓ / polylog ℓ, improving the previous inapproximability factor of ℓ^Ω(1) by Hirahara (FOCS 2022). Our inapproximability factor is optimal up to the polylog ℓ factor unless NP ⊆ coAM because the CMMSA problem with an approximation factor O(ℓ) is in coAM.

@InProceedings{STOC26p354, author = {Shuichi Hirahara and Mikito Nanashima}, title = {A Sharp Characterization of Pessiland}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {354-364}, doi = {10.1145/3798129.3800755}, year = {2026}, } Publisher's Version Article: stoc26main-p177-p doi:10.1145/3798129.3800755

Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb Inequalities
Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang
(University of California at Berkeley, USA; University of Michigan, USA; Massachusetts Institute of Technology, USA; Ohio State University, USA)
In coding theory, the problem of list recovery asks one to find all codewords c of a given code C which such that at least 1−ρ fraction of the symbols of c lie in some predetermined set of ℓ symbols for each coordinate of the code. A key question is bounding the maximum possible list size L of such codewords for the given code C.
In this paper, we give novel combinatorial bounds on the list recoverability of various families of linear and folded linear codes, including random linear codes, random Reed–Solomon codes, explicit folded Reed–Solomon codes, and explicit univariate multiplicity codes. Our main result is that in all of these settings, we show that for code of rate R, when ρ = 1 − R − є approaches capacity, the list size L is at most (ℓ/(R+є))^O(1+R/є). These results also apply in the average-radius regime. Our result resolves a long-standing open question on whether L can be bounded by a polynomial in ℓ. In the zero-error regime, our bound on L perfectly matches known lower bounds.
The primary technique is a novel application of a discrete entropic Brascamp–Lieb inequality to the problem of list recovery, allowing us to relate the local structure of each coordinate with the global structure of the recovered list. As a result of independent interest, we show that a recent result by Chen and Zhang (STOC 2025) on the list decodability of folded Reed–Solomon codes can be generalized into a novel Brascamp–Lieb type inequality.

@InProceedings{STOC26p365, author = {Joshua Brakensiek and Yeyuan Chen and Manik Dhar and Zihan Zhang}, title = {Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb Inequalities}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {365-376}, doi = {10.1145/3798129.3800756}, year = {2026}, } Publisher's Version Article: stoc26main-p178-p doi:10.1145/3798129.3800756

Complexity-Theoretic Universal Inductive Inference
Shuichi Hirahara and Mikito Nanashima
(National Institute of Informatics, Tokyo, Japan; Institute of Science Tokyo, Japan)
Solomonoff’s theory of universal inductive inference (Inf. Control., 1964) provides a framework for predicting a future observation from past ones generated by an arbitrary randomized Turing machine. The theory is founded on the notion of resource-unbounded Kolmogorov complexity, and thus Solomonoff’s approach cannot be realized as a finite-step algorithm.
In this paper, we develop a complexity-theoretic counterpart of Solomonoff’s theory. We construct a polynomial-time universal inductive inference algorithm that extrapolates a sequence of symbols generated by any unknown t-time randomized Turing machine in time polynomial in t, assuming that time-bounded Kolmogorov complexity can be computed in average polynomial time. Previously, it was not even known whether distributional learning for all polynomial-size circuits—an i.i.d. analogue of inductive inference—is feasible if NP is easy on average. Moreover, without any unproven assumption, we characterize a distribution of sequences for which there exists an efficient inductive inference algorithm by the notion of prequential compression. We also construct an optimal efficient inductive inference algorithm that performs as well as any other efficient algorithms.
Our universal inductive inference algorithm relies on (1) a new algorithmic proof of a chain rule for time-bounded algorithmic information, and (2) an online algorithm that boosts the “confidence” of our inductive inference algorithm.

@InProceedings{STOC26p377, author = {Shuichi Hirahara and Mikito Nanashima}, title = {Complexity-Theoretic Universal Inductive Inference}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {377-385}, doi = {10.1145/3798129.3800757}, year = {2026}, } Publisher's Version Article: stoc26main-p181-p doi:10.1145/3798129.3800757

Tâtonnement Dynamics for Fisher Markets with Chores
Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, and Tianlong Nan
(University of Illinois at Urbana-Champaign, USA; Columbia University, USA)
In this paper, we initiate the study of tâtonnement dynamics in markets with chores. Tâtonnement is a fundamental market dynamics, that captures how prices evolve when they are adjusted in proportion of their excess demand. While its convergence to a competitive equilibrium (CE) is well understood in goods markets for broad classes of utility functions, no analogous results are known for chore markets.
Analyzing tâtonnement in the chores market presents new challenges. Several elegant structural properties that facilitate convergence in goods markets—such as convexity of the equilibrium price set and monotonicity of excess demand under the tâtonnement price updates—fail to hold in the chore setting. Consistent with these difficulties, we first show that naïve tâtonnement, which adjusts prices proportional to the excess demand, diverges even for the simplest case of linear disutilities. To overcome this, we propose a modified process called relative tâtonnement, where prices are updated according to normalized excess demand. We prove its convergence to a CE under suitable step-size choices for a broad class of disutility functions, namely continuous, convex, and 1-homogeneous (CCH) disutilities. This class includes many standard forms such as linear and convex CES disutilities. Our proof proceeds by showing that the relative tâtonnement dynamics correspond to applying generalized gradient methods to a nonsmooth, nonconvex yet regular objective function—a generalization of the objective in the Eisenberg–Gale-type dual program introduced by Chaudhury, Kroer, Mehta, and Nan [EC 2024].
For the case of CES disutilities, where disutility is the p-norm of the individual chore disutilities for p ∈ (1, ∞), we show that relative tâtonnement converges to an ε-CE in Õ(1/ε²) iterations. This quadratic convergence rate is established by proving smoothness of the associated objective function. We achieve this by interpreting the objective as the polar gauge (or gauge dual) of the disutility function. Typically, smoothness of gauge dual is proven by proving strong convexity of the primal gauge, (in this case, the disutility function). Although CES disutilities are neither strictly nor strongly convex, we are nonetheless able to prove smoothness of their gauge dual, thereby obtaining the desired rate of convergence.
Finally, following the framework of Arrow and Hurvicz [Econometrica 1958], we analyze the stability of competitive equilibria under the continuous-time counterpart of our relative tâtonnement dynamics. We provide a complete characterization of local stability when agents have linear disutilities—offering a new normative justification for their desirability [Bogomolnaia, Moulin, Sandomirskiy, and Yanovskaya (Econometrica 2017)].
The full version of the paper is available at https://arxiv.org/abs/2511.21162.

@InProceedings{STOC26p386, author = {Bhaskar Ray Chaudhury and Christian Kroer and Ruta Mehta and Tianlong Nan}, title = {Tâtonnement Dynamics for Fisher Markets with Chores}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {386-397}, doi = {10.1145/3798129.3800758}, year = {2026}, } Publisher's Version Article: stoc26main-p183-p doi:10.1145/3798129.3800758

Instance-Optimal Quantum State Certification with Entangled Measurements
Ryan O'Donnell and Chirag Wadhwa
(Carnegie Mellon University, USA; University of Edinburgh, UK)
We consider the task of quantum state certification: given a description of a hypothesis state σ and multiple copies of an unknown state ρ, a tester aims to determine whether the two states are equal or є-far in trace distance. It is known that Θ(d/є²) copies of ρ are necessary and sufficient for this task, assuming the tester can make entangled measurements over all copies. However, these bounds are for a worst-case σ, and it is not known what the optimal copy complexity is for this problem on an instance-by-instance basis. While such instance-optimal bounds have previously been shown for quantum state certification when the tester is limited to measurements unentangled across copies, they remained open when testers are unrestricted in the kind of measurements they can perform.
We address this open question by proving nearly instance-optimal bounds for quantum state certification when the tester can perform fully entangled measurements. Analogously to the unentangled setting, we show that the optimal copy complexity for certifying σ is given by the worst-case complexity times the fidelity between σ and the maximally mixed state. We prove our lower bounds using a novel quantum analogue of the Ingster–Suslina method, which is likely to be of independent interest. This method also allows us to recover the Ω(d/є²) lower bound for mixedness testing, i.e., certification of the maximally mixed state, with a surprisingly simple proof.

@InProceedings{STOC26p398, author = {Ryan O'Donnell and Chirag Wadhwa}, title = {Instance-Optimal Quantum State Certification with Entangled Measurements}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {398-409}, doi = {10.1145/3798129.3800759}, year = {2026}, } Publisher's Version Article: stoc26main-p187-p doi:10.1145/3798129.3800759

Hesse’s Redemption: Efficient Convex Polynomial Programming
Lucas Slot, David Steurer, and Manuel Wiedmer
(University of Amsterdam, Netherlands; ETH Zurich, Switzerland)
Efficient algorithms for convex optimization, such as the ellipsoid method, require an a priori bound on the radius of a ball around the origin guaranteed to contain an optimal solution if one exists. For linear and convex quadratic programming, such solution bounds follow from classical characterizations of optimal solutions by systems of linear equations. For other programs, e.g., semidefinite ones, examples due to Khachiyan show that optimal solutions may require huge coefficients with an exponential number of bits, even if we allow approximations. Correspondingly, semidefinite programming is not even known to be in NP.
The unconstrained minimization of convex polynomials of degree four and higher has remained a fundamental open problem between these two extremes: its optimal solutions do not admit a linear characterization and, at the same time, Khachiyan-type examples do not apply. We resolve this problem by developing new techniques to prove solution bounds when no linear characterizations are available. Even for programs minimizing a convex polynomial (of arbitrary degree) over a polyhedron, we prove that the existence of an optimal solution implies that an approximately optimal one with polynomial bit length also exists. These solution bounds, combined with the ellipsoid method, yield the first polynomial-time algorithm for (approximate) convex polynomial programming, settling a question posed by Nesterov (Math. Program., 2019). Before, no polynomial-time algorithm was known even for unconstrained minimization of a convex polynomial of degree four.
Our results rely on a structural decomposition of any convex polynomial into a sum of a linear function and a polynomial on a linear subspace that admits a strongly convex lower bound, where the logarithm of the strong convexity parameter is polynomially bounded in the input size. A key component of our proof is a strong local-to-global property for convex polynomials: if at every point some directional second derivative vanishes, then a single directional second derivative must vanish everywhere. While Hesse erroneously claimed that this property holds for general polynomials (J. Reine Angew. Math., 1851), we show that it holds for convex ones.

@InProceedings{STOC26p410, author = {Lucas Slot and David Steurer and Manuel Wiedmer}, title = {Hesse’s Redemption: Efficient Convex Polynomial Programming}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {410-419}, doi = {10.1145/3798129.3800760}, year = {2026}, } Publisher's Version Article: stoc26main-p193-p doi:10.1145/3798129.3800760

Sparsifying Suprema of Gaussian Processes
Anindya De, Shivam Nadimpalli, Ryan O'Donnell, and Rocco A. Servedio
(University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Columbia University, USA)
We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let T be any (possibly infinite) bounded set of vectors in ⁿ, and let {_t := t · g }_{t∈ T} be the canonical Gaussian process on T, where g∼ N(0, I_n). We show that there is an O_ε(1)-size subset S ⊆ T and a set of real values {c_s}_{s ∈ S} such that the random variable sup_{s ∈ S} {X_s + c_s} is an ε-approximator (in L¹) of the random variable sup_{t ∈ T} X_t. Notably, the size of the sparsifier S is completely independent of both |T| and the ambient dimension n.
We give two applications of this sparsification theorem:
A “Junta Theorem” for Norms: We show that given any norm ν(x) on ⁿ, there is another norm ψ(x) depending only on the projection of x onto O_ε(1) directions, for which ψ(g) is a multiplicative (1 ± ε)-approximation of ν(g) with probability 1−ε for g ∼ N(0,I_n).
Sparsification of Convex Sets: We show that any intersection of (possibly infinitely many) halfspaces in ⁿ that are at distance r from the origin is ε-close (under N(0,I_n)) to an intersection of only O_r,ε(1) halfspaces. This yields new polynomial-time agnostic learning and tolerant property testing algorithms for intersections of halfspaces.

@InProceedings{STOC26p420, author = {Anindya De and Shivam Nadimpalli and Ryan O'Donnell and Rocco A. Servedio}, title = {Sparsifying Suprema of Gaussian Processes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {420-431}, doi = {10.1145/3798129.3800761}, year = {2026}, } Publisher's Version Article: stoc26main-p202-p doi:10.1145/3798129.3800761

Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds beyond Banaszczyk
Nikhil Bansal and Haotian Jiang
(University of Michigan, USA; University of Chicago, USA)
The Beck-Fiala Conjecture [Beck and Fiala, Discrete Appl. Math., 1981] asserts that any set system of n elements with degree k has combinatorial discrepancy O(√k). A substantial generalization is the Komlós Conjecture, which states that any m × n matrix with columns of unit ℓ₂ length has discrepancy O(1).
In this work, we resolve the Beck-Fiala Conjecture for k ≥ log² n. We also give an O(√k + √logn) bound for k ≤ log² n, where O(·) hides poly(loglogn) factors. These bounds improve upon the O(√k logn) bound in [Banaszczyk, Random Struct. Algor., 1998].
For the Komlós problem, we give an O(log^1/4 n) bound, improving upon the previous O(√logn) bound [Banaszczyk, Random Struct. Algor., 1998]. All of our results also admit efficient polynomial-time algorithms
To obtain these results, we exploit a new technique of “decoupling via affine spectral-independence” in designing rounding algorithms. In particular, our algorithms obtain the desired colorings via a discrete Brownian motion, guided by a semidefinite program (SDP). Besides standard constraints used in prior works, we add some extra affine spectral-independence constraints, which effectively decouple the evolution of discrepancies across different rows, and allow us to better control how many rows accumulate large discrepancies at any point during the process. This new technique is quite general and may be of independent interest.

@InProceedings{STOC26p432, author = {Nikhil Bansal and Haotian Jiang}, title = {Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds beyond Banaszczyk}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {432-442}, doi = {10.1145/3798129.3800762}, year = {2026}, } Publisher's Version Article: stoc26main-p206-p doi:10.1145/3798129.3800762

Derandomizing Matrix Concentration Inequalities from Free Probability
Robert Wang, Lap Chi Lau, and Hong Zhou
(University of Waterloo, Canada; Fuzhou University, China)
Recently, sharp matrix concentration inequalities were developed using the theory of free probability. In this work, we design polynomial time deterministic algorithms to construct outcomes that satisfy the guarantees of these inequalities. As direct consequences, we obtain polynomial time deterministic algorithms for the matrix Spencer problem and for constructing near-Ramanujan graphs. Our proofs show that the concepts and techniques in free probability are useful not only for mathematical analyses but also for efficient computations.

@InProceedings{STOC26p443, author = {Robert Wang and Lap Chi Lau and Hong Zhou}, title = {Derandomizing Matrix Concentration Inequalities from Free Probability}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {443-454}, doi = {10.1145/3798129.3800763}, year = {2026}, } Publisher's Version Article: stoc26main-p209-p doi:10.1145/3798129.3800763

On the Cryptographic Foundations of Interactive Quantum Advantage
Kabir Tomer and Mark Zhandry
(University of Illinois at Urbana-Champaign, USA; Stanford University, USA; NTT Research, USA)
In this work, we study the hardness required to achieve proofs of quantumness (PoQ), which in turn capture (potentially interactive) quantum advantage. A “trivial” or non-interactive PoQ simply assumes an (efficiently-verifiable) average-case hard problem for classical computers that is easy for quantum computers. However, there is much interest in “non-trivial” PoQs that actually rely on quantum hardness assumptions, instead of an assumed separation between quantum and classical computation for search problems, especially since these are often a starting point for more sophisticated protocols such as classical verification of quantum computation (CVQC). We show several lower-bounds for the hardness required to achieve non-trivial PoQ, specifically showing that they likely require cryptographic hardness, with different types of cryptographic hardness being required for different variations of non-trivial PoQ. In particular, our results help explain the challenges in using lattices to build publicly verifiable PoQ and its various extensions such as CVQC.

@InProceedings{STOC26p455, author = {Kabir Tomer and Mark Zhandry}, title = {On the Cryptographic Foundations of Interactive Quantum Advantage}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {455-466}, doi = {10.1145/3798129.3800764}, year = {2026}, } Publisher's Version Article: stoc26main-p217-p doi:10.1145/3798129.3800764

A Constant-Factor Approximation for Directed Latency
Jannis Blauth and Ramin Mousavi
(ETH Zurich, Switzerland; IDSIA at USI-SUPSI, Switzerland)
In the Directed Latency problem, we are given an asymmetric metric space (V ∪ {s},c) on a set V of clients and a depot s. We are looking for a path P starting in s that visits all clients and minimizes the sum of the clients’ waiting times (also known as latency) before being visited on the path. This models problems in logistics where client satisfaction is essential, as opposed to objectives like in TSP, where the goal is to make the salesperson as happy as possible.
In contrast to the symmetric version of this problem (also known as the Deliveryperson problem and the Traveling Repairperson problem in the literature), there are significant gaps in our understanding of Directed Latency. The best approximation factor has remained at O(log|V|), as shown by [Friggstad, Salavatipour, and Svitkina, ’13], for more than a decade. Only recently, [Friggstad and Swamy, ’22] presented a constant-factor approximation, but in quasi-polynomial time. Both results follow similar ideas: they consider buckets with geometrically increasing distances, build a path on each bucket, and then stitch together all these paths to get a feasible solution. Building a path on each bucket can be done cheaply thanks to developments in Asymmetric Path TSP. However, stitching these paths together incurs a logarithmic factor increase in the latency. [Friggstad and Swamy, ’22] showed that by guessing a client from each bucket and augmenting a standard LP relaxation with these guesses, one can reduce the stitching cost. Unfortunately, the number of buckets is logarithmic in the number of clients, so the running time of their algorithm is quasi-polynomial.
In this paper, we present the first constant-factor approximation for Directed Latency in polynomial time by introducing a completely new way of bucketing, which helps us strengthen a standard LP relaxation with less aggressive guessing. Although the resulting LP is no longer a relaxation of Directed Latency, it still admits a good solution. Then, we present a rounding algorithm for fractional solutions of our LP, which at a high level follows the rounding algorithm by [Friggstad and Swamy, ’22] but with many new ingredients, crucially exploiting the way we restricted the feasibility region of the LP formulation.

@InProceedings{STOC26p467, author = {Jannis Blauth and Ramin Mousavi}, title = {A Constant-Factor Approximation for Directed Latency}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {467-477}, doi = {10.1145/3798129.3800765}, year = {2026}, } Publisher's Version Article: stoc26main-p221-p doi:10.1145/3798129.3800765

Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime
Weiming Feng, Xiongxin Yang, Yixiao Yu, and Yiyao Zhang
(University of Hong Kong, Hong Kong; University of California at Santa Barbara, USA; Nanjing University, China)
We study the problem of learning an n-variables k-CNF formula Φ from its i.i.d. uniform random solutions, which is equivalent to learning a Boolean Markov random field (MRF) with k-wise hard constraints. Revisiting Valiant’s algorithm (Commun. ACM’84), we show that it can exactly learn (1) k-CNFs with bounded clause intersection size under Lovász local lemma type conditions, from O(logn) samples; and (2) random k-CNFs near the satisfiability threshold, from O(n^exp(−√k)) samples. These results significantly improve the previous O(n^k) sample complexity. We further establish new information-theoretic lower bounds on sample complexity for both exact and approximate learning from uniform random solutions.

@InProceedings{STOC26p478, author = {Weiming Feng and Xiongxin Yang and Yixiao Yu and Yiyao Zhang}, title = {Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {478-488}, doi = {10.1145/3798129.3800766}, year = {2026}, } Publisher's Version Article: stoc26main-p226-p doi:10.1145/3798129.3800766

The Complexity of Min-Max Optimization with Product Constraints
Martino Bernasconi and Matteo Castiglioni
(Bocconi University, Italy; Politecnico di Milano, Italy)
We study the computational complexity of the problem of computing local min-max equilibria of games with a nonconvex-nonconcave utility function f. From the work of Daskalakis, Skoulakis, and Zampetakis (STOC 2021), this problem was known to be hard in the restrictive case in which players are required to play strategies that are jointly constrained, leaving open the question of its complexity under more natural constraints. In this paper, we settle the question and show that the problem is PPAD-hard even under product constraints and, in particular, over the hypercube.

@InProceedings{STOC26p489, author = {Martino Bernasconi and Matteo Castiglioni}, title = {The Complexity of Min-Max Optimization with Product Constraints}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {489-499}, doi = {10.1145/3798129.3800767}, year = {2026}, } Publisher's Version Article: stoc26main-p227-p doi:10.1145/3798129.3800767

Better Neural Network Expressivity: Subdividing the Simplex
Egor Bakaev, Florestan Brunck, Christoph Hertrich, Jack Stade, and Amir Yehudayoff
(University of Copenhagen, Denmark; University of Technology Nuremberg, Germany; Technion, Israel)
This work studies the expressivity of ReLU neural networks with a focus on their depth. A sequence of previous works showed that ⌈ log₂(n+1) ⌉ hidden layers are sufficient to compute all continuous piecewise linear (CPWL) functions on ℝⁿ. Hertrich, Basu, Di Summa, and Skutella (NeurIPS ’21 / SIDMA ’23) conjectured that this result is optimal in the sense that there are CPWL functions on ℝⁿ, like the maximum function, that require this depth. We disprove the conjecture and show that ⌈log₃(n−1)⌉+1 hidden layers are sufficient to compute all CPWL functions on ℝⁿ.
A key step in the proof is that ReLU neural networks with two hidden layers can exactly represent the maximum function of five inputs. More generally, we show that ⌈log₃(n−2)⌉+1 hidden layers are sufficient to compute the maximum of n≥ 4 numbers. Our constructions almost match the ⌈log₃(n)⌉ lower bound of Averkov, Hojny, and Merkert (ICLR ’25) in the special case of ReLU networks with weights that are decimal fractions. The constructions have a geometric interpretation via polyhedral subdivisions of the simplex into “easier” polytopes.

@InProceedings{STOC26p500, author = {Egor Bakaev and Florestan Brunck and Christoph Hertrich and Jack Stade and Amir Yehudayoff}, title = {Better Neural Network Expressivity: Subdividing the Simplex}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {500-507}, doi = {10.1145/3798129.3800768}, year = {2026}, } Publisher's Version Article: stoc26main-p234-p doi:10.1145/3798129.3800768

On Zeros and Algorithms for Disordered Systems: Mean-Field Spin Glasses
Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, and Guus Regts
(CWI, Netherlands; Stanford University, USA; Massachusetts Institute of Technology, USA; University of Amsterdam, Netherlands)
Spin glasses are fundamental probability distributions at the core of statistical physics, the theory of average-case computational complexity, and modern high-dimensional statistical inference. In the mean-field setting, we design deterministic quasipolynomial-time algorithms for estimating the partition function to arbitrarily high accuracy for all inverse temperatures in the second moment regime. In particular, for the Sherrington--Kirkpatrick model, our algorithms succeed for the entire replica-symmetric phase. To achieve this, we study the locations of the zeros of the partition function. Notably, our methods are conceptually simple, and apply equally well to the spherical case and the case of Ising spins.

@InProceedings{STOC26p508, author = {Ferenc Bencs and Brice Huang and Daniel Z. Lee and Kuikui Liu and Guus Regts}, title = {On Zeros and Algorithms for Disordered Systems: Mean-Field Spin Glasses}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {508-517}, doi = {10.1145/3798129.3800769}, year = {2026}, } Publisher's Version Article: stoc26main-p245-p doi:10.1145/3798129.3800769

Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time
Angelo Farfan, Mehrdad Ghadiri, and Junzhao Yang
(Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA)
We present an algorithm that given any invertible symmetric diagonally dominant M-matrix (SDDM), i.e., a principal submatrix of a graph Laplacian, L and a nonnegative vector b, computes an entrywise approximation to the solution of L x = b in Õ(m n^o(1)) time with high probability, where m is the number of nonzero entries and n is the dimension of the system.

@InProceedings{STOC26p518, author = {Angelo Farfan and Mehrdad Ghadiri and Junzhao Yang}, title = {Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {518-528}, doi = {10.1145/3798129.3800770}, year = {2026}, } Publisher's Version Article: stoc26main-p247-p doi:10.1145/3798129.3800770

Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak
(McGill University, Canada; Ohio State University, USA)
We prove that the list replicability number of d-dimensional γ-margin half-spaces satisfies d/2+1 ≤ LR(H_γ^d) ≤ d. In particular, it grows with the dimension. Our lower bound uses a topological argument based on a local Borsuk–Ulam theorem. Our upper bound is proved by constructing a list-replicable learning rule from the generalization properties of SVMs. These bounds yield several consequences in learning theory and communication complexity.
In learning theory, we show that every disambiguation of infinite-dimensional large-margin half-spaces to a total concept class has unbounded Littlestone dimension, answering a question of Alon, Hanneke, Holzman, and Moran (FOCS 2021). We also show that the maximum list-replicability number of any finite set of points and homogeneous half-spaces in ℝ^d is d, resolving a problem of Chase, Moran, and Yehudayoff (FOCS 2023). In addition, we construct a partial concept class with Littlestone dimension 1 such that all its disambiguations have infinite Littlestone dimension, resolving a problem of Cheung, H. Hatami, P. Hatami, and Hosseini (ICALP 2023).
In communication complexity, we prove that every disambiguation of Gap Hamming Distance in the large-gap regime has unbounded public-coin randomized communication complexity, answering a question of Fang, Göös, Harms, and Hatami (STOC 2025). We also obtain an O(1) versus ω(1) separation between randomized and pseudo-deterministic communication complexity.

@InProceedings{STOC26p529, author = {Ari Blondal and Hamed Hatami and Pooya Hatami and Chavdar Lalov and Sivan Tretiak}, title = {Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {529-540}, doi = {10.1145/3798129.3800771}, year = {2026}, } Publisher's Version Article: stoc26main-p250-p doi:10.1145/3798129.3800771

Efficient Quantum Hermite Transform
Siddhartha Jain, Vishnu Iyer, Rolando D. Somma, Ning Bao, and Stephen Jordan
(University of Texas at Austin, USA; Google, USA; Northeastern University, USA; Brookhaven National Laboratory, USA)
We present a new primitive for quantum algorithms that implements a discrete Hermite transform efficiently, in time that is polylogarithmic in the dimension and the inverse of the allowable error. This transform, which maps basis states to states whose amplitudes are proportional to the Hermite functions, can be interpreted as the Gaussian analogue of the Fourier transform. Our algorithm is based on a method to exponentially fast-forward the evolution of the quantum harmonic oscillator, giving a simulation algorithm with nearly optimal circuit complexity for a fundamental Hamiltonian more than four decades after Feynman posed the simulation of quantum physics as an application of quantum computers.
We apply this Hermite transform to give examples of provable quantum query advantage in property testing and learning. In particular, we give algorithms whose complexity is independent of the number of variables to test the property of being close to a low-degree in the Hermite basis when inputs are sampled from the Gaussian distribution, and solve a Gaussian analogue of the Goldreich-Levin learning task, analogous to the Boolean function case. We also comment on other potential uses of this transform to simulating time dynamics of quantum systems in the continuum.

@InProceedings{STOC26p541, author = {Siddhartha Jain and Vishnu Iyer and Rolando D. Somma and Ning Bao and Stephen Jordan}, title = {Efficient Quantum Hermite Transform}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {541-552}, doi = {10.1145/3798129.3800772}, year = {2026}, } Publisher's Version Article: stoc26main-p255-p doi:10.1145/3798129.3800772

Optimal Random Self-Reductions for All Linear Problems
Shuichi Hirahara and Nobutaka Shimizu
(National Institute of Informatics, Tokyo, Japan; Institute of Science Tokyo, Japan)
The linear problem specified by an n × n matrix M over a finite field is the problem of computing the product of M and a given vector x. We present optimal error-tolerant random self-reductions (also known as worst-case to average-case reductions) for all linear problems: Given a linear-size circuit that computes M x on an ε-fraction of inputs x for a positive constant ε, we construct a randomized linear-size circuit that computes M x for all inputs x with high probability. This resolves the open problem posed by Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA’24), who presented quantum n^1.5-time random self-reductions for all linear problems. Somewhat surprisingly, we also demonstrate the quantum advantage of their quantum reduction over classical uniform algorithms, by proving that any classical subquadratic-time random self-reduction requires the advice complexity of Ω(log(1/ε) · logn), as long as the field size is at most 1/ε. We complement this advice complexity lower bound by presenting (1) a random self-reduction with the optimal advice complexity of O(log(1/ε) · logn) and (2) a uniform random self-reduction over a large finite field.

@InProceedings{STOC26p553, author = {Shuichi Hirahara and Nobutaka Shimizu}, title = {Optimal Random Self-Reductions for All Linear Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {553-564}, doi = {10.1145/3798129.3800773}, year = {2026}, } Publisher's Version Article: stoc26main-p264-p doi:10.1145/3798129.3800773

Determination of the Fifth Busy Beaver Value
Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Matthew L. House, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann
(Independent, USA; Jagiellonian University, Poland; Inria, Paris, France; Sofia University, Bulgaria; University of Georgia, USA; University of Warsaw, Poland; Independent, Slovakia; Independent, China; Independent, Poland; PRGM DEV, France; University of California at San Diego, USA; University of Waterloo, Canada; LTCI - Télécom Paris - Institut Polytechnique de Paris, France)
The Busy Beaver value S(n) is the maximum number of steps that an n-state 2-symbol Turing machine can perform from the all-zero tape before halting. S was historically introduced by Tibor Radó in 1962 as one of the simplest examples of an uncomputable function. We prove that S(5) = 47,176,870 using the Coq proof assistant. The proof enumerates 181,385,789 Turing machines with 5 states and, for each machine, decides whether it halts or not. Our result marks the first determination of a new Busy Beaver value in over 40 years and the first Busy Beaver value ever to be formally verified, attesting to the effectiveness of massively collaborative online research (bbchallenge.org).

@InProceedings{STOC26p565, author = {Justin Blanchard and Daniel Briggs and Konrad Deka and Nathan Fenner and Yannick Forster and Georgi Georgiev (Skelet) and Matthew L. House and Maja Kądziołka and Pavel Kropitz and Shawn Ligocki and mxdys and Mateusz Naściszewski and Tristan Stérin and Chris Xu and Jason Yuen and Théo Zimmermann}, title = {Determination of the Fifth Busy Beaver Value}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {565-574}, doi = {10.1145/3798129.3806376}, year = {2026}, } Publisher's Version Published Artifact Video Info Artifacts Available Article: stoc26main-p268-p doi:10.1145/3798129.3806376

Dynamic Meta-Kernelization
Christian Bertram, Deborah Haun, Mads Vestergaard Jensen, and Tuukka Korhonen
(University of Copenhagen, Denmark; KIT, Germany)
Kernelization studies polynomial-time preprocessing algorithms. Over the last 20 years, the most celebrated positive results of the field have been linear kernels for classical NP-hard graph problems on sparse graph classes. In this paper, we lift these results to the dynamic setting.
As the canonical example, Alber, Fellows, and Niedermeier [J. ACM 2004] gave a linear kernel for dominating set on planar graphs. We provide the following dynamic version of their kernel: Our data structure is initialized with an n-vertex planar graph G in O(n logn) amortized time, and, at initialization, outputs a planar graph K with OPT(K) = OPT(G) and |K| = O(OPT(G)), where OPT(·) denotes the size of a minimum dominating set. The graph G can be updated by insertions and deletions of edges and isolated vertices in O(logn) amortized time per update, under the promise that it remains planar. After each update to G, the data structure outputs O(1) updates to K, maintaining OPT(K) = OPT(G), |K| = O(OPT(G)), and planarity of K.
Furthermore, we obtain similar dynamic kernelization algorithms for all problems satisfying certain conditions on (topological-)minor-free graph classes. Besides kernelization, this directly implies new dynamic constant-approximation algorithms and improvements to dynamic FPT algorithms for such problems.
Our main technical contribution is a dynamic data structure for maintaining an approximately optimal protrusion decomposition of a dynamic topological-minor-free graph. Protrusion decompositions were introduced by Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh, and Thilikos [J. ACM 2016], and have since developed into a part of the core toolbox in kernelization and parameterized algorithms.

@InProceedings{STOC26p575, author = {Christian Bertram and Deborah Haun and Mads Vestergaard Jensen and Tuukka Korhonen}, title = {Dynamic Meta-Kernelization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {575-583}, doi = {10.1145/3798129.3800774}, year = {2026}, } Publisher's Version Article: stoc26main-p269-p doi:10.1145/3798129.3800774

Boolean Function Monotonicity Testing Requires (Almost) n^1/2 Queries
Mark Chen, Xi Chen, Hao Cui, William Pires, and Jonah Stockwell
(Columbia University, USA)
We show that for any constant c>0, any (two-sided error) adaptive algorithm for testing monotonicity of Boolean functions must have query complexity Ω(n^1/2−c). This improves the Ω(n^1/3) lower bound of Chen, Waingarten, and Xie (2017) and almost matches the Õ(√n) upper bound of Khot, Minzer and Safra (2018).

@InProceedings{STOC26p584, author = {Mark Chen and Xi Chen and Hao Cui and William Pires and Jonah Stockwell}, title = {Boolean Function Monotonicity Testing Requires (Almost) <i>n^1/2</i> Queries}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {584-594}, doi = {10.1145/3798129.3800775}, year = {2026}, } Publisher's Version Article: stoc26main-p270-p doi:10.1145/3798129.3800775

Separating QMA from QCMA with a Classical Oracle
John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, and Mark Zhandry
(Columbia University, USA; Ruhr-University Bochum, Germany; University of Washington, USA; Stanford University, USA)
We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA). The separating classical oracle we construct is for a decision problem we coin spectral Forrelation – the oracle describes two subsets of the boolean hypercube, and the computational task is to decide if there exists a quantum state whose standard basis measurement distribution is well supported on one subset while its Fourier basis measurement distribution is well supported on the other subset. This is equivalent to estimating the spectral norm of a “Forrelation” matrix between two sets that are accessible through membership queries.
Our lower bound derives from a simple observation that a query algorithm with a classical witness can be run multiple times to generate many samples from a distribution, while a quantum witness is a “use once” object. This observation allows us to reduce proving a QCMA lower bound to proving a sampling hardness result which does not simultaneously prove a QMA lower bound. To prove said sampling hardness result for QCMA, we observe that quantum access to the oracle can be compressed by expressing the problem in terms of bosons – a novel “second quantization” perspective on compressed oracle techniques, which may be of independent interest. Using this compressed perspective on the sampling problem, we prove the sampling hardness result, completing the proof.

@InProceedings{STOC26p595, author = {John Bostanci and Jonas Haferkamp and Chinmay Nirkhe and Mark Zhandry}, title = {Separating QMA from QCMA with a Classical Oracle}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {595-606}, doi = {10.1145/3798129.3800776}, year = {2026}, } Publisher's Version Article: stoc26main-p275-p doi:10.1145/3798129.3800776

Perfect Network Resilience in Polynomial Time
Matthias Bentert and Stefan Schmid
(TU Berlin, Germany; Fraunhofer SIT, Germany)
Modern communication networks support local fast rerouting mechanisms to quickly react to link failures: nodes store a set of conditional rerouting rules which define how to forward an incoming packet in case of incident link failures. Ideally, such rerouting mechanisms provide perfect resilience: any packet is routed from its source s to its target t as long as s and t are still connected in the underlying graph after the link failures. However, ensuring perfect resilience is algorithmically challenging as the rerouting decisions at any node v must rely solely on the local information available at v: the link from which a packet arrived at v (known as the in-port), the target of the packet, and the incident link failures at v. Already in their seminal paper at ACM PODC’12, Feigenbaum, Godfrey, Panda, Schapira, Shenker, and Singla showed that there are instances in which perfect resilience cannot be achieved. While the design of local rerouting algorithms has received much attention since then, we still lack a detailed understanding of when perfect resilience is achievable.
This paper closes this gap and presents a complete characterization of when perfect resilience can be achieved. This characterization also allows us to design an O(n)-time algorithm to decide whether a given instance is perfectly resilient and an O(nm)-time algorithm to compute perfectly resilient rerouting rules whenever it is. Our algorithm is also attractive for the simple structure of the rerouting rules it uses, known as skipping in the literature: alternative links are chosen according to an ordered priority list (per in-port), where failed links are simply skipped. This is also naturally supported in hardware. The size of such an encoding is in Θ(nm) and therefore the running time of our algorithm is optimal when considering skipping rerouting rules. Intriguingly, our result also implies that in the context of perfect resilience, skipping rerouting rules are as powerful as more general rerouting rules that define the out-port for each set of incident failed links explicitly. This partially answers a long-standing open question by Chiesa, Nikolaevskiy, Mitrovic, Gurtov, Madry, Schapira, and Shenker [IEEE/ACM Transactions on Networking, 2017] in the affirmative.
While our algorithm is simple, its analysis is intricate. A key concept in the analysis are links whose two endpoints also form a node separator. We prove that removing those links does not change whether a given instance is perfectly resilient or not. We also show that once all such links are removed, any instance either contains one of four specific rooted minors or belongs to one of three classes. If one of the four rooted minors is contained, then we are dealing with a no-instance (this was previously known for only two of them). Lastly, we show that any instance in any of the three remaining classes is a yes-instance, completing the characterization of perfectly resilient graphs. We do this by showing that simply following a particular face of a planar embedding of the reduced instance using the right-hand rule until a link directly to the target is found is sufficient.

@InProceedings{STOC26p607, author = {Matthias Bentert and Stefan Schmid}, title = {Perfect Network Resilience in Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {607-618}, doi = {10.1145/3798129.3800777}, year = {2026}, } Publisher's Version Article: stoc26main-p277-p doi:10.1145/3798129.3800777

From Random to Explicit via Subspace Designs with Applications to Local Properties and Matroids
Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang
(University of California at Berkeley, USA; University of Michigan, USA; Massachusetts Institute of Technology, USA; Ohio State University, USA)
In coding theory, a common question is to understand the threshold rates of various local properties of codes, such as their list decodability and list recoverability. A recent work Levi, Mosheiff, and Shagrithaya (FOCS 2025) gave a novel unified framework for calculating the threshold rates of local properties for random linear and random Reed–Solomon codes.
In this paper, we extend their framework to studying the local properties of subspace designable codes, including explicit folded Reed-Solomon and univariate multiplicity codes. Our first main result is a local equivalence between random linear codes and (nearly) optimal subspace design codes up to an arbitrarily small rate decrease. We show any local property of random linear codes applies to all subspace design codes. As such, we give the first explicit construction of folded linear codes that simultaneously attain all local properties of random linear codes. Conversely, we show that any local property which applies to all subspace design codes also applies to random linear codes. This connection was recently used by Brakensiek, Chen, Dhar, and Zhang to improve bounds on the combinatorial list recoverability of random linear codes.
Our second main result is an application to matroid theory. We show that the correctable erasure patterns in a maximally recoverable tensor code can be identified in deterministic polynomial time, assuming a positive answer to a matroid-theoretic question due to Mason (1981). This improves on a result of Jackson and Tanigawa (JCTB 2024) who gave a complexity characterization of RP ∩ coNP assuming a stronger conjecture. Our result also applies to the generic bipartite rigidity and matrix completion matroids.
As a result of additional interest, we study the existence and limitations of subspace designs. In particular, we tighten the analysis of family of subspace designs constructed by Guruswami and Kopparty (Combinatorica 2016) and show that better subspace designs do not exist over algebraically closed fields.

@InProceedings{STOC26p619, author = {Joshua Brakensiek and Yeyuan Chen and Manik Dhar and Zihan Zhang}, title = {From Random to Explicit via Subspace Designs with Applications to Local Properties and Matroids}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {619-630}, doi = {10.1145/3798129.3800778}, year = {2026}, } Publisher's Version Article: stoc26main-p281-p doi:10.1145/3798129.3800778

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
Prateek Dwivedi, Benedikt Pago, and Tim Seppelt
(IT University of Copenhagen, Denmark; University of Cambridge, UK)
Valiant's conjecture from 1979 asserts that the circuit complexity classes VP and VNP are distinct, meaning that the permanent does not admit polynomial-size algebraic circuits. As it is the case in many branches of complexity theory, the unconditional separation of these complexity classes seems elusive. In stark contrast, the symmetric analogue of Valiant's conjecture has been proven by Dawar and Wilsenach (ICALP 2020): the permanent does not admit symmetric algebraic circuits of polynomial size, while the determinant does. Symmetric algebraic circuits are both a powerful computational model and amenable to proving unconditional lower bounds.
In this paper, we develop a symmetric algebraic complexity theory by introducing symmetric analogues of the complexity classes VP, VBP, and VF called symVP, symVS, and symVF. They comprise polynomials that admit symmetric algebraic circuits, skew circuits, and formulas, respectively, of polynomial orbit size. Having defined these classes, we show unconditionally that symVF ⊊ symVS ⊊ symVP.
To that end, we characterise the polynomials in symVF and symVS as those that can be written as linear combinations of homomorphism polynomials for patterns of bounded treedepth and pathwidth, respectively. This extends a previous characterisation by Dawar, Pago, and Seppelt (ITCS 2026) of symVP. The separation follows via model-theoretic techniques and the theory of homomorphism indistinguishability.
Although symVS and symVP admit strong lower bounds, we are able to show that these complexity classes are rather powerful: They contain homomorphism polynomials which are VBP- and VP-complete, respectively. Vastly generalising previous results, we give general graph-theoretic criteria for homomorphism polynomials and their linear combinations to be VBP-, VP-, or VNP-complete. These conditional lower bounds drastically enlarge the realm of natural polynomials known to be complete for VNP, VP, or VBP. Under the assumption VFPT ≠ VW, we precisely identify the homomorphism polynomials that lie in VP as those whose patterns have bounded treewidth and thereby resolve an open problem posed by Saurabh (2016).

@InProceedings{STOC26p631, author = {Prateek Dwivedi and Benedikt Pago and Tim Seppelt}, title = {Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {631-640}, doi = {10.1145/3798129.3800779}, year = {2026}, } Publisher's Version Article: stoc26main-p286-p doi:10.1145/3798129.3800779

Kolmogorov’s Approach to P vs. NP: Chain Rules for Time-Bounded Kolmogorov Complexity
Valentine Kabanets and Antonina Kolokolova
(Simon Fraser University, Canada; Memorial University of Newfoundland, Canada)
Time-bounded conditional Kolmogorov complexity of a string x given y, K^t(x∣ y), is the length of a shortest program that, given y, prints x within t steps. The Chain Rule for conditional K^t with error e is the following hypothesis: there is a constant c such that, for any strings y,x₁,…,x_ℓ∈{0,1}^*, for any ℓ∈ℕ, and all sufficiently large time bounds t,
 K^t(x₁,…,x_ℓ∣ y) ≥ ℓ∑i=1
 K^tc(x_i ∣ y, x₁,…,x_i−1) − ℓ· O(logt) −e(N,t),  
where N=∑_i=1^ℓ |x_i|. When y=є (the empty string), we get the Chain Rule for K^t.
In the late 1960s, Kolmogorov suggested that disproving the Chain Rule for K^t may be a good approach to proving that P≠ NP. We make a step towards showing that the two may be equivalent. Namely, we pinpoint the worst-case complexity assumptions equivalent to Chain Rules for (conditional) K^t, and the probabilistic variant pKc^t, where pKc^t(x∣ y)≤ s iff K^t(x∣ y,r)≤ s for at least 2/3 of random strings r∈{0,1}^t.
Chain Rule for conditional K^t with error e(N,t)≤ o(N) is equivalent to the conjunction of the following two statements: (1) E⊄io SIZE[2^o(n)], and (2) GapMcK^tP∈ promise- P, where Gap McK^tP is a promise problem to distinguish between inputs (x,y,1^s) with K^t(x∣ y)≤ s and those with K^(t)(x∣ y)> s + o(|x|). Chain Rule for conditional pKc^t with error e(N,t)≤ o(N) is equivalent to Gap McpK^tP∈ promise- BPP, for the analog of Gap McK^tP for conditional pK^t. We get analogous equivalences for the case of unconditional K^t and pK^t (i.e., for y=є). These are the first exact complexity characterizations for natural versions of Chain Rules for time-bounded Kolmogorov complexity. Assuming Gap McK^tP is NP-hard (which is true under cryptographic assumptions [Huang et al., STOC’23], the equivalence above would simplify to “the Chain Rule for conditional K^t with error e(N,t)≤ o(N) holds iff NP=P”, which would completely validate Kolmogorov’s intuition. Among some other results, we present a natural promise- BPP-complete problem based on the problem of approximating pK^t(x∣ y) for short inputs x with |x|≤ logt, and give some algorithmic consequences if Gap McpK^tP were easy.

@InProceedings{STOC26p641, author = {Valentine Kabanets and Antonina Kolokolova}, title = {Kolmogorov’s Approach to P vs. NP: Chain Rules for Time-Bounded Kolmogorov Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {641-652}, doi = {10.1145/3798129.3800780}, year = {2026}, } Publisher's Version Article: stoc26main-p288-p doi:10.1145/3798129.3800780

Reviving Thorup’s Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, and Leon Schiller
(New York University, USA; Carnegie Mellon University, USA; ETH Zurich, Switzerland; INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; University of Michigan, USA; MPI-INF, Germany; Saarland University, Germany; Hasso Plattner Institute - University of Potsdam, Germany)
We aim to revive Thorup’s conjecture [Thorup, WG’92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph G=(V,E) with m edges, we can add m^1+o(1) “shortcut” edges E₊ from the transitive closure E^* of G so that _G+(u,v) ≤ m^o(1) for all (u,v)∈ E^*, where G₊=(V,E∪ E₊). The conjecture was refuted by Hesse [Hesse, SODA’03], followed by significant efforts in the last few years to optimize the lower bounds.
In this paper we observe that although Hesse refuted the letter of Thorup’s conjecture, his work [Hesse, SODA’03]—and all followup work —does not refute the spirit of the conjecture, which should allow G₊ to contain both new (shortcut) edges and new Steiner vertices. Our results are as follows.
On the positive side, we present explicit attacks that break all known shortcut lower bounds using Steiner vertices. On the negative side, we rule out ideal m^1+o(1)-size, m^o(1)-diameter shortcuts whose “thickness” is t=o(logn/loglogn), meaning no path can contain t consecutive Steiner vertices. We propose a candidate hard instance as the next step toward resolving the revised version of Thorup’s conjecture.
Finally, we show promising implications. Almost-optimal parallel algorithms for computing a generalization of the shortcut that approximately preserves distances or flows imply almost-optimal parallel algorithms with m^o(1) depth for exact shortcut paths and exact maximum flow. The state-of-the-art algorithms have much worse depth of n^1/2+o(1) [Rozhoň, Haeupler, Martinsson, STOC’23] and m^1+o(1) [Chen, Kyng, Liu, FOCS’22], respectively.

@InProceedings{STOC26p653, author = {Aaron Bernstein and Henry Fleischmann and Maximilian Probst Gutenberg and Bernhard Haeupler and Gary Hoppenworth and Yonggang Jiang and George Z. Li and Seth Pettie and Thatchaphol Saranurak and Leon Schiller}, title = {Reviving Thorup’s Shortcut Conjecture}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {653-664}, doi = {10.1145/3798129.3800781}, year = {2026}, } Publisher's Version Article: stoc26main-p292-p doi:10.1145/3798129.3800781

SNARGs for NP and Non-signaling PCPs, Revisited
Lalita Devadas, Samuel B. Hopkins, Yael Tauman Kalai, Pravesh K. Kothari, Alex Lombardi, and Surya Mathialagan
(Massachusetts Institute of Technology, USA; Princeton University, USA; NTT Research, USA)
We revisit the question of whether it is possible to build succinct non-interactive arguments (SNARGs) for all of NP under standard assumptions using non-signaling probabilistically checkable proofs [Kalai-Raz-Rothblum, STOC’ 14]. In particular, we observe that using exponential-length PCPs appears to circumvent all of the existing barriers.
For our main result, we give a candidate non-adaptive for NP and prove its soundness under: the learning with errors assumption (or other standard assumptions such as bilinear maps), and a mathematical conjecture about multivariate polynomials over the reals.
In more detail, our conjecture is an upper bound on the minimum total coefficient size of Nullstellensatz proofs (Potechin-Zhang, ICALP 2024) of membership in a concrete polynomial ideal. We emphasize that this is not a cryptographic assumption or any form of computational hardness assumption.
Of particular interest is the fact that our security analysis makes non-black-box use of the SNARG adversary, circumventing the black-box barrier of Gentry and Wichs (STOC ’11). This gives a blueprint for constructing non-adaptive SNARGs for NP that is not subject to the Gentry-Wichs barrier.

@InProceedings{STOC26p665, author = {Lalita Devadas and Samuel B. Hopkins and Yael Tauman Kalai and Pravesh K. Kothari and Alex Lombardi and Surya Mathialagan}, title = {SNARGs for NP and Non-signaling PCPs, Revisited}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {665-674}, doi = {10.1145/3798129.3800782}, year = {2026}, } Publisher's Version Article: stoc26main-p297-p doi:10.1145/3798129.3800782

A Meta-complexity Characterization of Minimal Quantum Cryptography
Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li
(University of Oxford, UK; Tsinghua University, China; University of Washington, USA; EPFL, Switzerland)
We give a meta-complexity characterization of EFI pairs, which are considered the “minimal” primitive in quantum cryptography (and are equivalent to quantum commitments). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy.
A key technical step in our proof, which may be of independent interest, is to show that the existence of EFI pairs is equivalent to the existence of non-uniform single-copy secure pseudorandom state generators (nu 1-PRS). As a corollary, we get an alternative, arguably simpler, construction of a universal EFI pair.

@InProceedings{STOC26p675, author = {Bruno Cavalar and Boyang Chen and Andrea Coladangelo and Matthew Gray and Zihan Hu and Zhengfeng Ji and Xingjian Li}, title = {A Meta-complexity Characterization of Minimal Quantum Cryptography}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {675-686}, doi = {10.1145/3798129.3800783}, year = {2026}, } Publisher's Version Info Article: stoc26main-p298-p doi:10.1145/3798129.3800783

Fast and Compact Random Mappings with Uniform Guarantees and Applications
Ying Feng and Piotr Indyk
(Massachusetts Institute of Technology, USA)
Random orthonormal or Gaussians maps from ℝⁿ to ℝ^m are a fundamental tool in geometric functional analysis, design of algorithms and machine learning. For example, it is known that, with high probability, a random mapping F from ℝⁿ to ℝ^m yields a (1+ε)-distortion embedding from ℓ₂ⁿ to ℓ₁^m, i.e., such that ||x||₂ ≤ ||Fx||₁ ≤ (1+ε) ||x||₂ for all x ∈ ℝⁿ, as long as m=Ω(n/ε²). However, the algorithmic applications of such mappings have been stymied by the Θ(nm) time needed to evaluate F x for a given x. Several alternative constructions of randomized mappings were proposed, with runtimes near-linear in n, but at the price of increasing the dimension m by poly-logarithmic factors.
In this paper, we give a new construction of randomized mappings that, in several settings, yields the best-known dimension bound of m=(n/ε²), while maintaining a near-linear mapping time. Our result applies to the general uniform approximations framework of Cherapanamjeri-Nelson’22. As a result, we obtain improved dimension bounds for applications such as ℓ₂ to ℓ₁ embeddings, adaptive distance estimation data structures, and more.

@InProceedings{STOC26p687, author = {Ying Feng and Piotr Indyk}, title = {Fast and Compact Random Mappings with Uniform Guarantees and Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {687-697}, doi = {10.1145/3798129.3800784}, year = {2026}, } Publisher's Version Article: stoc26main-p303-p doi:10.1145/3798129.3800784

Lower Estimates for 𝐿₁-Distortion of Transportation Cost Spaces
Chris Gartland and Mikhail Ostrovskii
(University of North Carolina at Charlotte, USA; St. John's University, USA)
Quantifying the degree of dissimilarity between two probability distributions on a finite metric space X is a fundamental task in Computer Science and Computer Vision. A natural dissimilarity measurement based on optimal transport is the earth mover’s distance (EMD), also known as the Kantorovich metric or Wasserstein-1 metric. We denote the metric space of probability measures on X equipped with the earth mover’s distance as EMD(X), called the earth mover’s space. A key technique for analyzing this metric – pioneered by Charikar and Indyk-Thaper – involves constructing low-distortion embeddings of EMD(X) into the Lebesgue space L₁. The best upper bound for the distortion of an embedding of EMD(X) with |X|=n into L₁ is O(logn). This result follows from a combination of Charikar’s work (which builds on work of Kleinberg and Tardos) and the seminal result by Fakcharoenphol, Rao, and Talwar. Moreover, it is well known that expander graphs yield a matching lower bound of Ω(logn) for L₁-distortion, showing that the upper bound can be tight.
It became a key problem to investigate whether the upper bound of O(logn) can be improved for important classes of metric spaces known to admit low-distortion embeddings into L₁. In the context of Computer Vision, grid graphs — especially planar grids — are among the most fundamental. Indyk posed the related problem of estimating the L₁-distortion of the space of uniform distributions on n-point subsets of ℝ². The Progress Report of Matoušek and Naor, last updated in August 2011, highlighted two key results: first, the work of Khot and Naor on Hamming cubes, which showed that the L₁-distortion of EMD({0,1}ⁿ) is of the order n, and second, the result of Naor and Schechtman for planar grids, which established that the L₁-distortion of EMD({0,…,n}²) is Ω(√logn).
Our first result is the improvement of the lower bound on the L₁-distortion of EMD({0,…,n}²) to Ω(logn), matching the universal upper bound up to multiplicative constants. The key ingredient allowing us to obtain these sharp estimates is a new Sobolev-type inequality for scalar-valued functions on the grid graphs. Our method is also applicable to many recursive families of graphs, such as diamond and Laakso graphs. We obtain the sharp distortion estimates of logn in these cases as well.

@InProceedings{STOC26p698, author = {Chris Gartland and Mikhail Ostrovskii}, title = {Lower Estimates for 𝐿₁-Distortion of Transportation Cost Spaces}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {698-709}, doi = {10.1145/3798129.3800785}, year = {2026}, } Publisher's Version Article: stoc26main-p304-p doi:10.1145/3798129.3800785

Approximating Gains-from-Trade in Matching Markets
Moshe Babaioff, Aviad Rubinstein, Xizhi Tan, and Kangning Wang
(Hebrew University of Jerusalem, Israel; Stanford University, USA; Rutgers University, USA)
A central challenge in mechanism design is to develop truthful trade mechanisms that maximize the expected gains-from-trade (GFT) in two-sided markets with strategic agents. As achieving the full GFT is generally impossible, much of the literature has focused on constant-factor approximations. Existing results, however, are limited to the highly structured settings of bilateral trade and double auctions, in which every buyer can trade with every seller.
We consider the significantly more general setting of two-sided matching markets with arbitrary downward-closed constraints on the family of allowed matchings. For this setting, we present a simple randomized truthful mechanism that guarantees a constant-factor approximation to the optimal expected GFT. This result also resolves an open problem posed by Cai, Goldner, Ma, and Zhao (2021).

@InProceedings{STOC26p710, author = {Moshe Babaioff and Aviad Rubinstein and Xizhi Tan and Kangning Wang}, title = {Approximating Gains-from-Trade in Matching Markets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {710-721}, doi = {10.1145/3798129.3800786}, year = {2026}, } Publisher's Version Article: stoc26main-p305-p doi:10.1145/3798129.3800786

Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang
(Tel Aviv University, Israel; Google Research, Israel; Purdue University, USA; Technion, Israel)
The fundamental theorem of statistical learning establishes that binary PAC learning is governed by a single parameter—the Vapnik-Chervonenkis (VC) dimension—which controls both learnability and sample complexity. Extending this characterization to multiclass classification has long been challenging, since the early work of Natarajan in the late 80’s that proposed the Natarajan dimension (Nat) as a natural analogue of the VC dimension. Daniely and Shalev-Shwartz (2014) introduced the DS dimension, later shown by Brukhim et al. (2022) to characterize multiclass learnability. Brukhim et al. (2022) also demonstrated that the Natarajan and DS dimensions can diverge arbitrarily, so that multiclass learning appears to be governed by DS rather than Nat. We show that the agnostic multiclass PAC sample complexity is in fact governed by two distinct dimensions. Specifically, we prove nearly tight agnostic sample complexity bounds that, up to logarithmic factors, take the form
DS^1.5 / є + Nat / є²  
where є is the excess risk. This bound is tight up to a √DS factor in the first lower-order term, nearly matching known Nat/є² and DS/є lower bounds. The first term reflects the DS-controlled regime, while the second reveals that the Natarajan dimension still dictates asymptotic behavior for small є. Thus, unlike in binary or online classification—where a single dimension (VC or Littlestone) controls both phenomena—multiclass learning inherently involves two structural parameters.
Our technical approach departs significantly from traditional agnostic learning methods based on uniform convergence or reductions-to-realizable techniques. A key ingredient is a novel online procedure, based on a self-adaptive multiplicative-weights algorithm which performs a label-space reduction. This approach may be of independent interest and find further applications.

@InProceedings{STOC26p722, author = {Alon Cohen and Liad Erez and Steve Hanneke and Tomer Koren and Yishay Mansour and Shay Moran and Qian Zhang}, title = {Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {722-733}, doi = {10.1145/3798129.3800787}, year = {2026}, } Publisher's Version Article: stoc26main-p308-p doi:10.1145/3798129.3800787

Quantum Circuit Lower Bounds in the Magic Hierarchy
Natalie Parham
(Columbia University, USA)
We introduce the magic hierarchy, a quantum circuit model that alternates between arbitrary-sized Clifford circuits and constant-depth circuits with two-qubit gates (QNC⁰). This model unifies existing circuit models, such as QAC_f⁰ and models with adaptive intermediate measurements. Despite its generality, we are able to prove nontrivial lower bounds.
We prove new lower bounds in the first level of the hierarchy, showing that certain explicit quantum states cannot be approximately prepared by circuits consisting of a Clifford circuit followed by QNC⁰. These states include ground states of some topologically ordered Hamiltonians and nonstabilizer quantum codes. Our techniques exploit the rigid structure of stabilizer codes and introduce an infectiousness property: if even a single state in a high distance code can be approximately prepared by one of these circuits, then the entire subspace must lie close to a perturbed stabilizer code. We also show that proving state preparation lower bounds beyond a certain level of the hierarchy would imply classical circuit lower bounds beyond the reach of current techniques in complexity theory.
More broadly, our techniques go beyond lightcone-based methods and highlight how the magic hierarchy provides a natural framework for connecting circuit complexity, condensed matter, and Hamiltonian complexity.

@InProceedings{STOC26p734, author = {Natalie Parham}, title = {Quantum Circuit Lower Bounds in the Magic Hierarchy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {734-743}, doi = {10.1145/3798129.3800788}, year = {2026}, } Publisher's Version Article: stoc26main-p310-p doi:10.1145/3798129.3800788

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
Xiao Mao and Aviad Rubinstein
(Stanford University, USA)
We present novel randomized approximation schemes for the Edit Distance (ED) problem and the Longest Common Subsequence (LCS) problem that, for any constant є>0, compute a (1+є)-approximation for ED and a (1−є)-approximation for LCS in time n² / 2^logΩ(1)(n) for two strings of total length at most n. This running time improves upon the classical quadratic-time dynamic programming algorithms by a quasi-polynomial factor.
Our results yield significant insights into fine-grained complexity: Firstly, for ED, prior work indicates that any exact algorithm cannot be improved beyond a few logarithmic factors without refuting established complexity assumptions [Abboud, Hansen, Vassilevska Williams, Williams, 2016]; our quasi-polynomial speed-up shows a separation the complexity of approximate ED from that of exact ED, even for approximation factor arbitrarily close to 1. Secondly, for LCS, obtaining similar approximation-time tradeoffs via deterministic algorithms would imply breakthrough circuit lower bounds [Chen, Goldwasser, Lyu, Rothblum, Rubinstein, 2019]; our randomized algorithm demonstrates derandomization hardness for LCS approximation.

@InProceedings{STOC26p744, author = {Xiao Mao and Aviad Rubinstein}, title = {Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {744-754}, doi = {10.1145/3798129.3800789}, year = {2026}, } Publisher's Version Article: stoc26main-p322-p doi:10.1145/3798129.3800789

Trust Region Interior Point Methods: Optimal ℓ₂- and Faster Wide-Neighborhood Path Following
Daniel Dadush, Haoyuan Ma, Bento Natura, and László A. Végh
(CWI, Netherlands; University of Bonn, Germany; Columbia University, USA)
We present improved running time and iteration complexities of interior point methods for linear programs paramet­rized by the straight line complexity, i.e., the minimum number of segments of any piecewise linear curve traversing a particular neighborhood of the central path. While the standard measure of progress is the reduction in duality gap, the straight line complexity provides a stronger instance-wise bound, reflecting the combinatorial structure of the problem.
Our first main result is a wide-neighborhood interior point method whose running time is the wide-neighborhood straight line complexity times current matrix multiplication time, improving in essence a factor n over the algorithm by Allamigeon, Dadush, Loho, Natura, and Végh (SIAM J. Comput. 2025). The algorithm can be seen as a boosted version of the robust interior point methods of Cohen, Lee and Song (JACM 2021) and van den Brand (SODA 2020) that can reduce the gap by a polynomial factor in current matrix multiplication time. Our algorithm is also able to traverse any near-linear segments of the central path in current matrix multiplication time, independently of the length of the segment.
Our second main result focuses on interior point methods that stay in the narrow ℓ₂-neighborhood. We give a much stronger analysis of the ℓ₂-trust region interior point method introduced by Lan, Monteiro and Tsuchiya (SIAM J. Optim. 2009), showing that it is approximately instance optimal in this neighborhood: the number of iterations is within a constant factor of the lower bound.
A main ingredient in both methods are trust region subroutines with ℓ_∞ and ℓ₂-constraints, respectively. We develop fast and strongly polynomial algorithms for solving both these problems to high accuracy. In the ℓ₂-setting, this answers an open question by Lan, Monteiro and Tsuchiya.

@InProceedings{STOC26p755, author = {Daniel Dadush and Haoyuan Ma and Bento Natura and László A. Végh}, title = {Trust Region Interior Point Methods: Optimal ℓ₂- and Faster Wide-Neighborhood Path Following}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {755-766}, doi = {10.1145/3798129.3800790}, year = {2026}, } Publisher's Version Article: stoc26main-p331-p doi:10.1145/3798129.3800790

High-Accuracy List-Decodable Mean Estimation
Ziyun Chen, Spencer Compton, Daniel M. Kane, and Jerry Li
(University of Washington, USA; Stanford University, USA; University of California at San Diego, USA)
In list-decodable learning, we are given a set of data points such that an α-fraction of these points come from a “nice” distribution D, for some small α ≪ 1, and the goal is to output a short list of candidate solutions, such that at least one element of this list recovers some non-trivial information about D. By now, there is a large body of work on this topic; however, while many algorithms can achieve optimal list size in terms of α, all known algorithms must incur error which decays, in some cases quite poorly, with 1 / α. In this paper, we ask if this is inherent: is it possible to trade off list size with accuracy in list-decodable learning? More formally, given ε > 0, can we output a slightly larger list in terms of α and ε, but so that one element of this list has error at most ε with the ground truth? We call this problem high-accuracy list-decodable learning.
Our main result is that non-trivial high-accuracy guarantees, both information-theoretically and algorithmically, are possible for the canonical setting of list-decodable mean estimation of identity-covariance Gaussians. Specifically, we demonstrate that there exists a list of candidate means of size at most L = exp( O( log² 1 / α/ε² )) so that one of the elements of this list has ℓ₂ distance at most ε to the true mean. We also design an algorithm that outputs such a list with runtime and sample complexity n = d^O(logL) + expexp(O(logL)). In particular, our results demonstrate that in the natural regime where α and ε are both small constants, it is possible to achieve error ≤ 0.01 in fully-polynomial time, where all prior work suffered error which was much larger than 1. We do so by demonstrating a completely novel proof of identifiability, as well as a new algorithmic way of leveraging this proof without the sum-of-squares hierarchy, which may be of independent technical interest.

@InProceedings{STOC26p767, author = {Ziyun Chen and Spencer Compton and Daniel M. Kane and Jerry Li}, title = {High-Accuracy List-Decodable Mean Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {767-776}, doi = {10.1145/3798129.3800791}, year = {2026}, } Publisher's Version Article: stoc26main-p335-p doi:10.1145/3798129.3800791

On the Informativeness of Moments in Optimal Stopping
José Correa, Andrés Cristi, Vasilis Livanos, Victor Verdugo, and Jiechen Zhang
(Universidad de Chile, Chile; EPFL, Switzerland; Center for Mathematical Modeling, Chile; Pontificia Universidad Católica de Chile, Chile)
We study a variant of the prophet inequality with limited information, where the decision maker has access only to the first k moments of each random variable, rather than their full distributions. In this work, we show that even with full moment knowledge (i.e., k=∞), the best possible competitive ratio is Θ(1/ logn), and that this can already be achieved with only knowledge of the first moment. While the lower bound is simple and is attained by a standard exponential bucketing algorithm, the upper bound requires a subtle construction. This involves using Vandermonde matrices first to construct a parametrized family of distributions for which the first k moments coincide, and for which the expected maximum of n such copies varies widely across different parameter choices. Using Prokhorov’s theorem, we establish the existence of limit distributions, which we show have all their moments equal. Finally, we describe a construction where an adversary can select equally looking instances combining these distributions, making it impossible for the decision maker to obtain a factor better than O(1/ logn) of the expected maximum.
Our result implies that to obtain improved prophet inequalities, further assumptions beyond moment knowledge are needed. To showcase this direction, we establish improved bounds under additional distributional assumptions such as MHR and bounded coefficient of variation.

@InProceedings{STOC26p777, author = {José Correa and Andrés Cristi and Vasilis Livanos and Victor Verdugo and Jiechen Zhang}, title = {On the Informativeness of Moments in Optimal Stopping}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {777-787}, doi = {10.1145/3798129.3800792}, year = {2026}, } Publisher's Version Article: stoc26main-p342-p doi:10.1145/3798129.3800792

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
Jiawei Li, Yuhao Li, and Hanlin Ren
(University of Texas at Austin, USA; Columbia University, USA; Institute for Advanced Study at Princeton, USA)
We study the *refuter* problems for proof complexity lower bounds. Suppose ϕ is a hard tautology that does not admit any length-s proof in some proof system P. In the corresponding refuter problem, we are given (query access to) a purported length-s proof π in P that claims to have proved ϕ, and our goal is to find an invalid derivation step within π. As suggested by witnessing theorems in bounded arithmetic, the *computational complexity* of these refuter problems is closely tied to the *metamathematics* of the underlying lower bounds.
We focus on refuter problems corresponding to lower bounds for *resolution*, which is arguably the single most studied system in proof complexity. As a warm-up, we show that many refuter problems for resolution *width* lower bounds are PLS-complete. To capture the complexity of refuter problems for resolution *size* lower bounds, we introduce a new class rwPHP(PLS) in decision-tree TFNP, which can be seen as a randomized version of PLS.
First, we show that the refuter problems for many resolution size lower bounds can be solved in rwPHP(PLS), including the classic lower bound of Haken [TCS, 1985] for the pigeonhole principle. More generally, we identify a common proof technique that we call ”random restriction + width lower bound”, and present strong evidence that resolution lower bounds proved by this technique typically have refuter problems in rwPHP(PLS).
We then show that the refuter problem for *any* resolution size lower bound is rwPHP(PLS)-hard, thereby demonstrating that the rwPHP(PLS) upper bound mentioned above is tight. Informally speaking, this means that ”rwPHP(PLS)-reasoning” is *necessary* for proving *all* resolution size lower bounds.
Interpreted in bounded arithmetic, our results show that the theory T₂¹(α) + dwPHP(PV(α)) characterizes the ”reasoning power” required to prove (the ”easiest”) resolution size lower bounds.
As a corollary, we obtain surprisingly efficient proofs of resolution lower bounds. In particular, we show that many resolution size lower bounds can be proved in low-width *random resolution* [Pudlák–Thapen, CCC’17].

@InProceedings{STOC26p788, author = {Jiawei Li and Yuhao Li and Hanlin Ren}, title = {Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {788-798}, doi = {10.1145/3798129.3800793}, year = {2026}, } Publisher's Version Article: stoc26main-p343-p doi:10.1145/3798129.3800793

Testing Noisy Low-Degree Polynomials for Sparsity
Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, and Nathan White
(University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; Columbia University, USA)
We consider the problem of testing if an unknown low-degree polynomial p over ℝⁿ is sparse versus far from sparse, given access to noisy evaluations of the polynomial p at randomly chosen points. This is a natural property-testing version of various well-studied problems about learning low-degree sparse polynomials in the presence of noise, and is a generalization of the work of Chen, De, and Servedio (2020), on testing noisy linear functions for sparsity, to the more challenging setting of low-degree polynomials.
Our main result gives a precise characterization of when sparsity testing for low-degree polynomials can be carried out with constant sample complexity independent of dimension, along with a constant-sample algorithm for this problem in the parameter regime where this is possible. In more detail, for any mean-zero variance-one finitely supported distribution X over the reals, any degree parameter d, and any sparsity parameters s and T ≥ s, we define a computable function MSG_X,d(·) (short for ”maximum sparsity gap”), and:
For T ≥ MSG_X,d(s) we give an O_s,X,d(1)-sample algorithm for the problem of distinguishing whether a degree-d multilinear polynomial over ℝⁿ is s-sparse versus ε-far from T-sparse, given independent labeled examples (x,p(x)+noise)_{x ∼ X^{⊗ n}}. (Crucially, this sample complexity is completely independent of the ambient dimension n.) On the other hand,
For T ≤ MSG_X,d(s) − 1, we show that even in the absence of noise, any algorithm for distinguishing whether a multilinear degree-d polynomial is s-sparse versus -far from T-sparse, given independent labeled examples (x,p(x))_{x ∼ X^{⊗ n}}, must use Ω_X,d,s(logn) examples.
Our techniques employ a generalization of the results of Dinur, Friedgut, Kindler, and O’Donnell (2007) on the Fourier tails of bounded functions over {±1}ⁿ to a broad range of finitely supported distributions, which may be of independent interest.

@InProceedings{STOC26p799, author = {Yiqiao Bao and Anindya De and Shivam Nadimpalli and Rocco A. Servedio and Nathan White}, title = {Testing Noisy Low-Degree Polynomials for Sparsity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {799-805}, doi = {10.1145/3798129.3800794}, year = {2026}, } Publisher's Version Article: stoc26main-p348-p doi:10.1145/3798129.3800794

Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes
Fernando Granha Jeronimo and Nikhil Shagrithaya
(University of Illinois at Urbana-Champaign, USA; University of Michigan at Ann Arbor, USA)
We present a general framework for derandomizing random linear codes with respect to a broad class of properties, known as local properties, which encompass several standard notions such as distance, list-decoding, list-recovery, and perfect hashing. Our approach extends the classical Alon–Edmonds–Luby (AEL) construction through a modified formalism of local coordinate-wise linear (LCL) properties, introduced by Levi, Mosheiff, and Shagrithaya (2025). The main theorem demonstrates that if random linear codes satisfy the complement of an LCL property P with high probability, then one can construct explicit codes satisfying the complement of P as well, with an enlarged yet constant alphabet size. This gives the first explicit constructions for list recovery, as well as special cases (e.g., list recovery with erasures, zero-error list recovery, perfect hash matrices), with parameters matching those of random linear codes. More broadly, our constructions realize the full range of parameters associated with these properties at the same level of optimality as in the random setting, thereby offering a systematic pathway from probabilistic guarantees to explicit codes that attain them. Furthermore, our derandomization of random linear codes also admits efficient (list) decoding via recently developed expander-based decoders.

@InProceedings{STOC26p806, author = {Fernando Granha Jeronimo and Nikhil Shagrithaya}, title = {Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {806-813}, doi = {10.1145/3798129.3800795}, year = {2026}, } Publisher's Version Article: stoc26main-p352-p doi:10.1145/3798129.3800795

Average Hardness of SIVP for Module Lattices of Fixed Rank
Koen de Boer, Aurel Page, Radu Toma, and Benjamin Wesolowski
(Unaffiliated, Netherlands; Inria - Univ. Bordeaux - CNRS - Bordeaux INP - IMB - UMR 5251, France; Sorbonne Univ. - Univ. Paris Cité - CNRS - IMJ-PRG, France; ENS de Lyon - CNRS - UMPA - UMR 5669, France)
The problem of finding short vectors in Euclidean lattices is a central hard problem in complexity theory. The case of module lattices (i.e., lattices which are also modules over a number ring) is of particular interest for cryptography and computational number theory. The hardness of finding short vectors in the asymptotic regime where the rank (as a module) is fixed is supporting the security of quantum-resistant cryptographic standards such as ML-DSA and ML-KEM.
In this article we prove the average-case hardness of this problem for uniformly random module lattices (with respect to the natural invariant measure on the space of module lattices of any fixed rank). More specifically, we prove a polynomial-time worst-case to average-case self-reduction for the approximate Shortest Independent Vector Problem (γ-SIVP) where the average case is the (discretized) uniform distribution over module lattices, with a polynomially-bounded loss in the approximation factor, assuming the Extended Riemann Hypothesis.
This result was previously known only in the rank-1 case (so-called ideal lattices). That proof critically relied on the fact that the space of ideal lattices is a compact group. In higher rank, the space is neither compact nor a group. Our main tool to overcome the resulting challenges is the theory of automorphic forms, which we use to prove a new quantitative rapid equidistribution result for random walks in the space of module lattices.

@InProceedings{STOC26p814, author = {Koen de Boer and Aurel Page and Radu Toma and Benjamin Wesolowski}, title = {Average Hardness of SIVP for Module Lattices of Fixed Rank}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {814-822}, doi = {10.1145/3798129.3800796}, year = {2026}, } Publisher's Version Article: stoc26main-p353-p doi:10.1145/3798129.3800796

Contention Resolution, with and without a Global Clock
Zixi Cai, Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie, and Ben Plosk
(Tsinghua University, China; Bar-Ilan University, Israel; University of Michigan, USA)
In the Contention Resolution problem n parties each wish to have exclusive use of a shared resource for one unit of time. A canonical example is n devices that each must broadcast a packet of information on a shared channel, but the same principles apply to other distributed systems. The problem has been studied since the early 1970s, under a variety of assumptions on feedback (collision detection, etc.) given to the parties, how the parties wake up (synchronized, adversarial, random), knowledge of n, and so on. The most consistent assumption is that parties do not have access to a global clock, only their local time since wake-up. This is surprising because the assumption of a global clock is both technologically realistic and algorithmically interesting. It enriches the problem, and opens the door to entirely new techniques.
In this paper we explore the power of the GlobalClock model and establish several new complexity separations, both between GlobalClock and the usual model, and within the LocalClock model. Our primary results are:
GlobalClock vs. LocalClock. We design a new Contention Resolution protocol that guarantees latency
 O((nloglognlog⁽³⁾ nlog⁽⁴⁾ n⋯ log^(log* n) n)· 2^log* n),  
which is n(loglogn)^1+o(1), in expectation and with high probability. This already establishes at least a roughly-logn complexity gap between randomized protocols in GlobalClock and LocalClock.
In-Expectation vs. With-High-Probability. Prior analyses of randomized Contention Resolution protocols in LocalClock guaranteed a certain latency with high probability, i.e., with probability 1−1/poly(n). We observe that it is just as natural to measure expected latency, and prove a logn-factor complexity gap between the two objectives for memoryless protocols. The In-Expectation complexity is Θ(n logn/loglogn) whereas the With-High-Probability latency is Θ(nlog² n/loglogn). Three of these four upper and lower bounds are new.
No Universally Optimal Protocols. Given the complexity separation above, one would naturally want a Contention Resolution protocol that is optimal under both the In-Expectation and With-High-Probability metrics. This is impossible! It is even impossible to achieve In-Expectation latency o(nlog² n/(loglogn)²) and With-High-Probability latency nlog^O(1) n simultaneously.

@InProceedings{STOC26p823, author = {Zixi Cai and Kuowen Chen and Shengquan Du and Tsvi Kopelowitz and Seth Pettie and Ben Plosk}, title = {Contention Resolution, with and without a Global Clock}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {823-834}, doi = {10.1145/3798129.3800797}, year = {2026}, } Publisher's Version Article: stoc26main-p360-p doi:10.1145/3798129.3800797

Fast Mixing of Quantum Spin Chains at All Temperatures
Thiago Bergamaschi and Chi-Fang Chen
(University of California at Berkeley, USA; Massachusetts Institute of Technology, USA)
It is shown that every one-dimensional Hamiltonian with short-range interactions admits a quantum Gibbs sampler [CKG23] with a system-size independent spectral gap at all finite temperatures. Consequently, their Gibbs states can be prepared in polylogarithmic depth, and satisfy exponential clustering of correlations, generalizing [Ara69].

@InProceedings{STOC26p835, author = {Thiago Bergamaschi and Chi-Fang Chen}, title = {Fast Mixing of Quantum Spin Chains at All Temperatures}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {835-844}, doi = {10.1145/3798129.3800798}, year = {2026}, } Publisher's Version Article: stoc26main-p363-p doi:10.1145/3798129.3800798

Magic and Communication Complexity
Uma Girish, Alex May, Natalie Parham, and Henry Yuen
(Columbia University, USA; Perimeter Institute for Theoretical Physics, Canada)
We establish novel connections between magic in quantum circuits and communication complexity. In particular, we show that functions computable with low magic have low communication cost.
Our first result shows that the D|| (deterministic simultaneous message passing) cost of a Boolean function f is at most the number of single-qubit magic gates in a quantum circuit computing f with any quantum advice state. If we allow mid-circuit measurements and adaptive circuits, we obtain an upper bound on the two-way communication complexity of f in terms of the magic + measurement cost of the circuit for f. As an application, we obtain magic-count lower bounds of Ω(n) for the n-qubit generalized Toffoli gate as well as the n-qubit quantum multiplexer.
Our second result gives a general method to transform Q||^* protocols (simultaneous quantum messages with shared entanglement) into R||^* protocols (simultaneous classical messages with shared entanglement) which incurs only a polynomial blowup in the communication and entanglement complexity, provided the referee’s action in the Q||^* protocol is implementable in constant T-depth. The resulting R||^* protocols satisfy strong privacy constraints and are PSM^* protocols (private simultaneous message passing with shared entanglement), where the referee learns almost nothing about the inputs other than the function value. As an application, we demonstrate n-bit partial Boolean functions whose R||^* complexity is polylog(n) and whose (interactive randomized) complexity is n^Ω(1), establishing the first exponential separations between R||^* and R for Boolean functions.

@InProceedings{STOC26p845, author = {Uma Girish and Alex May and Natalie Parham and Henry Yuen}, title = {Magic and Communication Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {845-856}, doi = {10.1145/3798129.3800799}, year = {2026}, } Publisher's Version Article: stoc26main-p364-p doi:10.1145/3798129.3800799

Average-Case Complexity of Quantum Stabilizer Decoding
Andrey Boris Khesin, Jonathan Lu, Alexander Poremba, Akshar Ramkumar, and Vinod Vaikuntanathan
(University of Oxford, UK; Massachusetts Institute of Technology, USA; Boston University, USA; California Institute of Technology, USA)
Random classical linear codes are widely believed to be hard to decode. While slightly sub-exponential time algorithms exist when the coding rate vanishes sufficiently rapidly, all known algorithms at constant rate require exponential time. By contrast, the complexity of decoding a random quantum stabilizer code has remained an open question for quite some time. This work closes the gap in our understanding of the algorithmic hardness of decoding random quantum versus random classical codes. We prove that decoding a random stabilizer code with even a single logical qubit is at least as hard as decoding a random classical code at constant rate--the maximally hard regime. This result suggests that the easiest random quantum decoding problem is at least as hard as the hardest random classical decoding problem, and shows that any sub-exponential algorithm decoding a typical stabilizer code, at any rate, would immediately imply a breakthrough in cryptography.
More generally, we also characterize many other complexity-theoretic properties of stabilizer codes. While classical decoding admits a random self-reduction, we prove significant barriers for the existence of random self-reductions in the quantum case. This result follows from new bounds on Clifford entropies and Pauli mixing times, which may be of independent interest. As a complementary result, we demonstrate various other self-reductions which are in fact achievable, such as between search and decision. We also demonstrate several ways in which quantum phenomena, such as quantum degeneracy, force several reasonable definitions of stabilizer decoding--all of which are classically identical--to have distinct or non-trivially equivalent complexity.

@InProceedings{STOC26p857, author = {Andrey Boris Khesin and Jonathan Lu and Alexander Poremba and Akshar Ramkumar and Vinod Vaikuntanathan}, title = {Average-Case Complexity of Quantum Stabilizer Decoding}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {857-868}, doi = {10.1145/3798129.3800800}, year = {2026}, } Publisher's Version Article: stoc26main-p373-p doi:10.1145/3798129.3800800

Clifford Testing: Algorithms and Lower Bounds
Marcel Hinsche, Zongbo Bao, Philippe van Dordrecht, Jens Eisert, Jop Briët, and Jonas Helsen
(FU Berlin, Germany; CWI, Netherlands; QuSoft, Netherlands)
We consider the problem of Clifford testing, which asks whether a black-box n-qubit unitary is a Clifford unitary or at least ε-far from every Clifford unitary. We give the first 4-query Clifford tester, which decides this problem with probability poly(ε). This contrasts with the minimum of 6 copies required for the closely-related task of stabilizer testing. We show that our tester is tolerant, by adapting techniques from tolerant stabilizer testing to our setting. In doing so, we settle in the positive a conjecture of Bu, Gu and Jaffe, by proving a polynomial inverse theorem for a non-commutative Gowers 3-uniformity norm. We also consider the restricted setting of single-copy access, where we give an O(n)-query Clifford tester that requires no auxiliary memory qubits or adaptivity. We complement this with a lower bound, proving that any such, potentially adaptive, single-copy algorithm needs at least Ω(n^1/4) queries. To obtain our results, we leverage the structure of the commutant of the Clifford group, obtaining several technical statements that may be of independent interest.

@InProceedings{STOC26p869, author = {Marcel Hinsche and Zongbo Bao and Philippe van Dordrecht and Jens Eisert and Jop Briët and Jonas Helsen}, title = {Clifford Testing: Algorithms and Lower Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {869-873}, doi = {10.1145/3798129.3800801}, year = {2026}, } Publisher's Version Article: stoc26main-p379-p doi:10.1145/3798129.3800801

Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits
Lijie Chen, Avishay Tal, and Yichuan Wang
(University of California at Berkeley, USA)
Proving lower bounds against depth-2 linear threshold circuits (a.k.a. THR ∘ THR) is one of the frontier questions in complexity theory. Despite tremendous effort, our best lower bounds for THR ∘ THR only hold for sub-quadratic number of gates, which was proven a decade ago by Tamaki (ECCC TR16) and Alman, Chan, and Williams (FOCS 2016) for a hard function in E^NP.
In this work, we prove that there is a function f ∈ E^NP that requires n^2.5−ε-size THR ∘ THR circuits for any ε > 0. We obtain our new results by designing a new 2^{n − nΩ(ε)}-time algorithm for estimating the acceptance probability of an XOR of two n^2.5−ε-size THR ∘ THR circuits, and apply Williams’ algorithmic method to obtain the desired lower bound.

@InProceedings{STOC26p874, author = {Lijie Chen and Avishay Tal and Yichuan Wang}, title = {Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {874-885}, doi = {10.1145/3798129.3800802}, year = {2026}, } Publisher's Version Article: stoc26main-p385-p doi:10.1145/3798129.3800802

Deterministic Hardness of Approximation of Unique-SVP and GapSVP in ℓ_p Norms for p>2
Yahli Hecht and Muli Safra
(Tel Aviv University, Israel)
We establish deterministic hardness of approximation results for the Shortest Vector Problem in ℓ_p norm (SVP_p) and for Unique-SVP (uSVP_p) for all p > 2. Previously, no deterministic hardness results were known, except for ℓ_∞.
For every p > 2, we prove constant-ratio hardness: no polynomial-time algorithm approximates the gap version of SVP_p or uSVP_p within a ratio of √2 − o(1), assuming 3SAT ∉ DTIME(2^O(n2/3logn)), and, resp., Unambiguous-3SAT (U-3SAT) ∉ DTIME(2^O(n2/3logn)).
We also show that for any ε > 0 there exists p_ε> 2 such that for every p ≥ p_ε: no polynomial-time algorithm approximates SVP_p within a ratio of 2^(logn)1−ε, assuming NP ⊈ DTIME(n^(logn)ε); and within a ratio of n^{1/(loglog(n))ε}, assuming NP ⊈ SUBEXP. This improves upon [Haviv, Regev, Theory of Computing 2012], which obtained similar inapproximation ratios under randomized reductions. We obtain analogous results for uSVP_p under the assumptions U-3SAT ⊈DTIME(n^(logn)ε) and U-3SAT ⊈SUBEXP, improving the previously known 1+o(1) [Stephens-Davidowitz, Approx 2016].
Strengthening the hardness of uSVP has a cryptographic impact. By the reduction of Lyubashevsky and Micciancio [Lyubashevsky, Micciancio, CRYPTO 2009], hardness for γ–uSVP_p carries over to 1/γ–BDD_p (Bounded Distance Decoding).

@InProceedings{STOC26p886, author = {Yahli Hecht and Muli Safra}, title = {Deterministic Hardness of Approximation of Unique-SVP and GapSVP in ℓ<i>_p</i> Norms for <i>p&gt;2</i>}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {886-897}, doi = {10.1145/3798129.3800803}, year = {2026}, } Publisher's Version Article: stoc26main-p388-p doi:10.1145/3798129.3800803

Strong ETH Holds for Bounded-Depth Resolution over Parities
Klim Efremenko and Dmitry Itsykson
(Ben-Gurion University of the Negev, Israel)
Strong lower bounds of the form 2^(1−є)n, where n is the number of variables and є>0 is arbitrarily small (i.e., bounds consistent with the Strong ETH), are exceptionally rare in proof complexity. The seminal work of Beck and Impagliazzo (STOC 2013) achieved such a bound for regular resolution, and the strongest extension known prior to our work was proved for O(є)-regular resolution by Bonacina and Talebanfard (Algorithmica, 2017).
We establish similar lower bounds for a significantly stronger proof system — a fragment of resolution over parities (Res(⊕)). This fragment captures Depth-n Res(⊕), and thus our result implies SETH-type lower bounds for both tree-like and regular Res(⊕). The core of our approach is a lossless lifting achieved by assigning distinct, randomly chosen gadgets to each variable.
Our result also yields a SETH-type lower bound for Depth-n resolution — a result that was previously unknown. We additionally provide a direct and simplified proof for this special case, which may be of independent interest.

@InProceedings{STOC26p898, author = {Klim Efremenko and Dmitry Itsykson}, title = {Strong ETH Holds for Bounded-Depth Resolution over Parities}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {898-909}, doi = {10.1145/3798129.3800804}, year = {2026}, } Publisher's Version Article: stoc26main-p393-p doi:10.1145/3798129.3800804

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
Sayan Bhattacharya, Ruoxu Cen, and Debmalya Panigrahi
(University of Warwick, UK; Duke University, USA)
We give the first algorithms for fully dynamic set cover with non-trivial worst-case guarantees for both recourse and update time. Specifically, we achieve O(logn) recourse and f· log(n) update time in the worst-case, for both approximation regimes: O(logn) and O(f) approximation. Prior to our work, all results for this problem either settled for amortized bounds on recourse and update time, or obtained f· log(n) update time in the worst-case but at the cost of Ω(m) worst-case recourse. (Here, m, n, f respectively denote the number of sets, maximum number of elements, and maximum frequency.)

@InProceedings{STOC26p910, author = {Sayan Bhattacharya and Ruoxu Cen and Debmalya Panigrahi}, title = {Fully Dynamic Set Cover: Worst-Case Recourse and Update Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {910-921}, doi = {10.1145/3798129.3800805}, year = {2026}, } Publisher's Version Article: stoc26main-p395-p doi:10.1145/3798129.3800805

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
Nick Fischer
(MPI-INF, Germany)
The APSP Hypothesis states that the All-Pairs Shortest Paths (APSP) problem requires time n^3−o(1) on graphs with polynomially bounded integer edge weights. Two increasingly stronger assumptions are the Strong APSP Hypothesis and the Directed Unweighted APSP Hypothesis which state that the fastest-known APSP algorithms on graphs with small weights and unweighted graphs, respectively, are best-possible. In this paper we design an efficient universe reduction for APSP, which proves that these three hypotheses are in fact equivalent, conditioned on ω = 2 and a plausible additive combinatorics assumption.
Along the way we resolve the fine-grained complexity of many long-standing graph and matrix problems with ”intermediate” complexity such as Node-Weighted APSP, All-Pairs Bottleneck Paths, Monotone Min-Plus Product in certain settings, and many others, by designing matching APSP-based lower bounds.

@InProceedings{STOC26p922, author = {Nick Fischer}, title = {Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {922-932}, doi = {10.1145/3798129.3800806}, year = {2026}, } Publisher's Version Article: stoc26main-p396-p doi:10.1145/3798129.3800806

Can Like Attract Like? A Study of Homonymous Gathering in Networks
Stéphane Devismes, Yoann Dieudonné, and Arnaud Labourel
(MIS - Université de Picardie Jules Verne, France; LIS - Aix-Marseille University, France)
A team of mobile agents, starting from distinct nodes of a network modeled as an undirected graph, have to meet at the same node and simultaneously declare that they all met. Agents execute the same algorithm, which they start when activated by an adversary or when an agent enter their initial node. While executing their algorithm, agents move from node to node by traversing edges of the network in synchronous rounds. Their perceptions and interactions are always strictly local: they have no visibility beyond their current node and can communicate only with agents occupying the same node. This task, known as gathering, is one of the most fundamental problems in distributed mobile systems. Over the past decades, numerous gathering algorithms have been designed, with a particular focus on minimizing their time complexity, i.e., the worst-case number of rounds between the start of the earliest agent and the completion of the task. To solve gathering deterministically, a common widespread assumption is that each agent initially has an integer ID, called label, only known to itself and that is distinct from those of all other agents. Labels play a crucial role in breaking possible symmetries, which, when left unresolved, may make gathering impossible. But must all labels be pairwise distinct to guarantee deterministic gathering?
In this paper, we conduct a deep investigation of this question by considering a context in which each agent applies a deterministic algorithm and has a label that may be shared with one or more other agents called homonyms. A team L of mobile agents, represented as the multiset of its labels, is said to be gatherable if, for every possible initial setting of L, there exists an algorithm, even dedicated to that setting, that solves gathering. Our contribution is threefold. First, we give a full characterization of the gatherable teams. Second, we design an algorithm that gathers all of them in poly(n,logλ) time, where n (resp. λ) is the order of the graph (resp. the smallest label in the team). This algorithm requires the agents to initially share only O(logloglogµ) bits of common knowledge, where µ is the multiplicity index of the team, i.e., the largest label multiplicity in L. Lastly, we show this dependency is almost optimal in the precise sense that no algorithm can gather every gatherable team in poly(n,logλ) time, with initially o(logloglogµ) bits of common knowledge.
As a by-product, we get the first deterministic poly(n,logλ)-time algorithm that requires no common knowledge to gather any team in the classical case where all agent labels are pairwise distinct. While this was known to be achievable for teams of exactly two agents, extending it to teams of arbitrary size—under the same time and knowledge constraints—faced a major obstacle inherently absent in the two-agent scenario: that of termination detection. The synchronization techniques that enable us to overcome this obstacle may be of independent interest, as termination detection is a key issue in distributed systems.

@InProceedings{STOC26p933, author = {Stéphane Devismes and Yoann Dieudonné and Arnaud Labourel}, title = {Can Like Attract Like? A Study of Homonymous Gathering in Networks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {933-942}, doi = {10.1145/3798129.3800807}, year = {2026}, } Publisher's Version Article: stoc26main-p403-p doi:10.1145/3798129.3800807

Steiner Forest: A Simplified Better-Than-2 Approximation
Anupam Gupta and Vera Traub
(New York University, USA; ETH Zurich, Switzerland)
In the Steiner Forest problem, we are given a graph with edge lengths, and a collection of demand pairs; the goal is to find a subgraph of least total length such that each demand pair is connected in this subgraph. For over twenty years, the best approximation ratio known for the problem was a 2-approximation due to Agrawal, Klein, and Ravi (STOC 1991), despite many attempts to surpass this bound. Finally, in a recent breakthrough, Ahmadi, Gholami, Hajiaghayi, Jabbarzade, and Mahdavi (FOCS 2025) gave a 2−є-approximation, where є ≈ 10⁻¹¹.
In this work, we show how to simplify and extend the work of Ahmadi et al. to obtain an improved 1.994-approximation. We combine some ideas from their work (e.g., an extended run of the moat-growing primal-dual algorithm, and identifying autarkic pairs) with other ideas—submodular maximization to find components to contract, as in the relative greedy algorithms for Steiner tree, and the use of autarkic triples. We hope that our cleaner abstraction will open the way for further improvements.

@InProceedings{STOC26p943, author = {Anupam Gupta and Vera Traub}, title = {Steiner Forest: A Simplified Better-Than-2 Approximation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {943-954}, doi = {10.1145/3798129.3800808}, year = {2026}, } Publisher's Version Article: stoc26main-p404-p doi:10.1145/3798129.3800808

Lower Bounds for Near-Quadratic-Depth Resolution over Parities
Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, and Russell Impagliazzo
(Tata Institute of Fundamental Research, Mumbai, India; University of California at San Diego, USA)
Resolution over parities (Res(⊕)) is a proof system introduced by Itsykson and Sokolov [MFCS ’14] as a stepping stone towards proving AC⁰[2]-Frege lower bounds. A recent line of work has established lower bounds against depth-restricted Res(⊕) refutations. Prior to this work, the state of the art was exponential lower bounds against depth O(N logN) Res(⊕) proved by Efremenko and Itsykson [CCC ’25], where N is the number of variables in the CNF. In this work we prove exponential lower bounds against depth O(N^2−є) Res(⊕) refutations. The lifted Tseitin formula we consider has O(N) clauses of width 6, which lets the allowed depth be almost quadratic not only in the number of variables, but also in the CNF size. We also prove depth-restricted lower bounds for variants of the bit pigeonhole principle (BPHP), including an exponential lower bound for depth O(n^2−є) Res(⊕) refutations of BPHP with n+1 pigeons and n holes.

@InProceedings{STOC26p955, author = {Sreejata Kishor Bhattacharya and Farzan Byramji and Arkadev Chattopadhyay and Russell Impagliazzo}, title = {Lower Bounds for Near-Quadratic-Depth Resolution over Parities}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {955-966}, doi = {10.1145/3798129.3800809}, year = {2026}, } Publisher's Version Article: stoc26main-p416-p doi:10.1145/3798129.3800809

New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
Jin-Yi Cai, Austen Fan, Shuai Shao, and Zhuxiao Tang
(University of Wisconsin-Madison, USA; University of Science and Technology of China, China)
We prove a complete complexity classification theorem for the planar eight-vertex model. For every parameter setting in ℂ for the eight-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) #P-hard for general graphs but computable in P-time for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. In (2), we discover new P-time computable eight-vertex models on planar graphs beyond Kasteleyn’s algorithm for counting planar perfect matchings. They are obtained by a combinatorial transformation to the planar Even Coloring problem followed by a holographic transformation to the tractable cases in the planar six-vertex model. In the process, we also encounter non-local connections between the planar eight vertex model and the bipartite Ising model, conformal lattice interpolation and Möbius transformation from complex analysis. The proof also makes use of cyclotomic fields.

@InProceedings{STOC26p967, author = {Jin-Yi Cai and Austen Fan and Shuai Shao and Zhuxiao Tang}, title = {New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {967-978}, doi = {10.1145/3798129.3800810}, year = {2026}, } Publisher's Version Article: stoc26main-p428-p doi:10.1145/3798129.3800810

Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints
Sepehr Assadi, Max Jiang, and Mars Xiang
(University of Waterloo, Canada)
In the semi-streaming model, we have an n-vertex graph G=(V,E) whose edges arrive in an arbitrary order in a stream. The goal is to make one or a few passes over the stream, use a limited memory of Õ(n) := O(n · polylogn) bits, and output a solution to the problem at hand at the end. A central open question in this area is to determine the best approximation ratio possible for the maximum matching problem via single-pass semi-streaming algorithms.
This problem admits a simple 0.5-approximation algorithm—by maintaining a maximal matching greedily—which, despite extensive efforts, has remained the state of the art. Lower bounds for this problem have also been few and far between with best known bounds ruling out better than 1/(1+ln(2)) ∼ 0.590 approximation, using a highly complicated construction motivated by the literature on Ruzsa-Szemeredi (RS) graphs from extremal graph theory.
We develop a new framework for proving lower bounds for the semi-streaming matching problem. Our framework abstracts out the extremal graph theory and information theoretic arguments in the lower bounds, and reduces the problem to constructing certain constant-size graphs, which we call blueprints. Not only can existing lower bounds be captured by these blueprints—leading to far simpler and more concise arguments—but also we can design new blueprints that can be used to rule out (8−2√10)/3 ∼ 0.558-approximation for the semi-streaming matching problem. We believe this approach can be of its own independent interest and lead to further improvements on this tantalizing open question.

@InProceedings{STOC26p979, author = {Sepehr Assadi and Max Jiang and Mars Xiang}, title = {Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {979-990}, doi = {10.1145/3798129.3800811}, year = {2026}, } Publisher's Version Article: stoc26main-p429-p doi:10.1145/3798129.3800811

Zero-Free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma Regime
Jingcheng Liu and Yixiao Yu
(Nanjing University, China)
We show that for q-colorings in k-uniform hypergraphs with maximum degree Δ, if k≥ 50 and q≥ 700Δ^5/k−10, there is a “Lee-Yang” zero-free strip around the interval [0,1] of the partition function, which includes the special case of uniform enumeration of hypergraph colorings. As an immediate consequence, we obtain Berry-Esseen type inequalities for hypergraph q-colorings under such conditions, demonstrating the asymptotic normality for the size of any color class in a uniformly random coloring. Our framework also extends to the study of “Fisher zeros”, leading to deterministic algorithms for approximating the partition function in the zero-free region.
Our approach is based on extending the recent work of [Liu, Wang, Yin, Yu, STOC 2025] to general constraint satisfaction problems (CSP). We focus on partition functions defined for CSPs by introducing external fields to the variables. A key component in our approach is a projection-lifting scheme, which enables us to essentially lift information percolation type analysis for Markov chains from the real line to the complex plane. Last but not least, we also show a Chebyshev-type inequality under the sampling LLL condition for atomic CSPs.

@InProceedings{STOC26p991, author = {Jingcheng Liu and Yixiao Yu}, title = {Zero-Free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma Regime}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {991-1002}, doi = {10.1145/3798129.3800812}, year = {2026}, } Publisher's Version Article: stoc26main-p435-p doi:10.1145/3798129.3800812

Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks
Ishan Chakraborty, Tanmay Inamdar, Ariel Kulik, Madhumita Kundu, and Saket Saurabh
(Institute of Mathematical Sciences, India; IIT Jodhpur, India; Ben-Gurion University of the Negev, Israel; University of Bergen, Norway)
In the last decade, FPT approximation has witnessed tremendous growth, with the development of several powerful upper- and lower-bound techniques. Within this framework, a newly emerging direction focuses on problems that admit algorithms with running time of the form c^k · n^O(1) for some constant c. This line of inquiry naturally leads to the notion of time–approximation ratio trade-offs (or time-ratio trade-offs): by relaxing the approximation guarantee in a controlled manner, one can improve the exponential dependence on the parameter in the running time. The contribution of this paper is threefold: (i) a formal language for parameterized randomized branching algorithms (called Oracle Subset Problems); (ii) a meta-algorithm applicable to all problems expressible in this language; and (iii) new time–ratio trade-offs obtained by instantiating the framework on fundamental problems, including Above-Guarantee Vertex Cover (parameterized by excess over the LP lower bound), Odd Cycle Transversal, Node Multiway Cut, Subset/Group Feedback Vertex Set, Min-Weight d-SAT, and Matroid-Rank d-Hitting Set (where solution is measured by the rank in a matroid accessible via an independence oracle), among others. Our applications demonstrate substantially broader applicability. For the first time, they apply to cut problems, problems with parity constraints (Odd Cycle Transversal), “complex” cycle hitting problems (hitting all cycles whose length mod73 is non-zero), and even a generalization where the user specifies the subset of vertices such that only the cycles passing through that subset of vertices should be hit. These results are obtained by developing time–ratio trade-offs for two meta-algorithms, expressed in our language: (i) the biased-graph framework [Wahlström, SODA 2017; Lee and Wahlström, arXiv 2020], and (ii) the Vertex Cover above LP framework [Lokshtanov et al., TALG 2014].
The core idea of our meta-algorithm is to design generic randomized FPT procedures whose behavior is captured by two-variable recurrences modeled as random walks. These walks go beyond existing analyses (e.g., [Kulik and Shachnai, FOCS 2020]): they are non-monotone, asymmetric, and in some cases include mandatory moves—steps that must be taken, or the walk (and the algorithm) fails. We believe that our Oracle Subset Problems language is robust, and that the accompanying meta-algorithm should find applications well beyond the scope of this paper.

@InProceedings{STOC26p1003, author = {Ishan Chakraborty and Tanmay Inamdar and Ariel Kulik and Madhumita Kundu and Saket Saurabh}, title = {Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1003-1013}, doi = {10.1145/3798129.3800813}, year = {2026}, } Publisher's Version Article: stoc26main-p443-p doi:10.1145/3798129.3800813

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
Bernhard Haeupler, Yaowei Long, Antti Roeyskoe, and Thatchaphol Saranurak
(INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; University of Michigan, USA)
A fault-tolerant distance labeling scheme assigns a label to each vertex and edge of an undirected weighted graph G with n vertices so that, for any edge set F of size |F| ≤ f, one can approximate the distance between p and q in G ∖ F by reading only the labels of F ∪ {p,q}.
For any k, we present a deterministic polynomial-time scheme with O(k⁴) approximation and Õ(f⁴n^1/k) label size. This is the first scheme to achieve a constant approximation while handling any number of edge faults f, resolving the open problem posed by Dory and Parter [Dory and Parter, PODC 2021]. All previous schemes provided only a linear-in-f approximation [Dory and Parter, PODC 2021; Long, Pettie, Saranurak, SODA 2025].
Our labeling scheme directly improves the state of the art in the simpler setting of distance sensitivity oracles. Even for just f = Θ(logn) faults, all previous oracles either have super-linear query time, linear-in-f approximation [Chechik, Langberg, Peleg, Roditty, Algorithmica 2012], or exponentially worse 2^poly(k) approximation dependency in k [Haeupler, Long, Saranurak, FOCS 2024].

@InProceedings{STOC26p1014, author = {Bernhard Haeupler and Yaowei Long and Antti Roeyskoe and Thatchaphol Saranurak}, title = {A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1014-1024}, doi = {10.1145/3798129.3800814}, year = {2026}, } Publisher's Version Article: stoc26main-p454-p doi:10.1145/3798129.3800814

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
Sándor Kisfaludi-Bak and Dániel Marx
(Aalto University, Espoo, Finland; CISPA Helmholtz Center for Information Security, Germany)
We give approximation schemes for Subset TSP and Steiner Tree on unit disk graphs, and more generally, on intersection graphs of similarly sized connected fat (not necessarily convex) polygons in the plane. As a first step towards this goal, we prove spanner-type results: finding an induced subgraph of bounded size that is (1+ε)-equivalent to the original instance in the sense that the optimum value increases only by a factor of at most (1+ε) when the solution can use only the edges in this subgraph. For Subset TSP, our algorithms find a (1+ε)-equivalent induced subgraph of size poly(1/ε)· OPT in polynomial time, and use it to find a (1+ε)-approximate solution in time 2^poly(1/ε)· n^O(1). For Steiner Tree, our algorithms find a (1+ε)-equivalent induced subgraph of size 2^poly(1/ε)· OPT in time 2^poly(1/ε)· n^O(1), and use it to find a (1+ε)-approximate solution in time 2^2poly(1/ε)· n^O(1). An improved algorithm finds a (1+ε)-approximate solution for Steiner Tree in time 2^poly(1/ε)· n^O(1). An easy reduction shows that approximation schemes for unit disks imply approximation schemes for planar graphs. Thus our results are far-reaching generalizations of analogous results of Klein [STOC’06] and Borradaile, Klein, and Mathieu [ACM TALG’09] for Subset TSP and Steiner Tree in planar graphs. We show that our results are best possible in the sense that dropping any of (i) similarly sized, (ii) connected, or (iii) fat makes both problems APX-hard.

@InProceedings{STOC26p1025, author = {Sándor Kisfaludi-Bak and Dániel Marx}, title = {Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1025-1036}, doi = {10.1145/3798129.3800815}, year = {2026}, } Publisher's Version Article: stoc26main-p460-p doi:10.1145/3798129.3800815

Breaking Barriers for Distributed MIS by Faster Degree Reduction
Seri Khoury and Aaron Schild
(INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; Google Research, USA)
We study the problem of finding a maximal independent set (MIS) in the standard LOCAL model of distributed computing. Classical algorithms by Luby [JACM’86] and Alon, Babai, and Itai [JALG’86] find an MIS in O(logn) rounds in n-node graphs with high probability. Despite decades of research, the existence of any o(logn)-round algorithm for general graphs remains one of the major open problems in the field.
Interestingly, the hard instances for this problem must contain constant-length cycles. This is because there exists a sublogarithmic-round algorithm for graphs with super-constant girth; i.e., graphs where the length of the shortest cycle is ω(1) , as shown by Ghaffari [SODA’16]. Thus, resolving this ≈ 40-year-old open problem requires understanding the family of graphs that contain k-cycles for some constant k.
In this work, we come very close to resolving this ≈ 40-year-old open problem by presenting a sublogarithmic-round algorithm for graphs that can contain k-cycles for all k > 6. Specifically, our algorithm finds an MIS in O(logΔ/log(log^* Δ) + poly(loglogn)) rounds, as long as the graph does not contain cycles of length ≤ 6, where Δ is the maximum degree of the graph. As a result, we push the limit on the girth of graphs that admit sublogarithmic-round algorithms from k = ω(1) all the way down to a small constant k=7. Moreover, our result has the two further implications.
First, it refutes a conjecture about MIS in trees. By combining our algorithm with a low-arboricity-to-low-degree reduction by Barenboim, Elkin, Pettie, and Schneider [JACM’16], we achieve an O(√logn/log(log^* n)) -round algorithm in trees. This refutes a conjecture in the book by Barenboim and Elkin that finding an MIS in trees requires Θ(√logn) rounds.
Secondly, it separates MIS from Maximal Matching (MM) in trees. Together with a very recent work that shows a Ω(√logn) lower bound for MM in trees, our result implies a surprising and counterintuitive separation between MIS and MM in trees. While MM can only be easier than MIS in general graphs, it becomes strictly harder in trees. This also implies that MIS itself is strictly harder to solve in general graphs than in trees.

@InProceedings{STOC26p1037, author = {Seri Khoury and Aaron Schild}, title = {Breaking Barriers for Distributed MIS by Faster Degree Reduction}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1037-1048}, doi = {10.1145/3798129.3800816}, year = {2026}, } Publisher's Version Article: stoc26main-p470-p doi:10.1145/3798129.3800816

Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos
(Royal Holloway University of London, UK; University of Liverpool, UK; University of Oxford, UK; University of Essex, UK)
We study the problem of computing a competitive equilibrium with approximately optimal bundles in Fisher markets with separable piecewise-linear concave (SPLC) utility functions, meaning that every buyer receives a (1−δ)-optimal bundle, instead of a perfectly optimal one. We establish the first intractability result for the problem by showing that it is PPAD-hard for some constant δ > 0, assuming the PCP-for-PPAD conjecture. This hardness result holds even if all buyers have identical budgets (competitive equilibrium with equal incomes), linear capped utilities, and even if we also allow ε-approximate clearing instead of perfect clearing, for any constant ε < 1/9. Importantly, we show that the PCP-for-PPAD conjecture is in fact required to show hardness for constant δ: showing PPAD-hardness for finding such approximate market equilibria in a broad class of markets encompassing those generated by our hardness result would prove the conjecture. This is the first natural problem where the conjecture is provably required to establish hardness for it.

@InProceedings{STOC26p1049, author = {Argyrios Deligkas and John Fearnley and Alexandros Hollender and Themistoklis Melissourgos}, title = {Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1049-1060}, doi = {10.1145/3798129.3800817}, year = {2026}, } Publisher's Version Article: stoc26main-p474-p doi:10.1145/3798129.3800817

Space-Efficient Text Indexing with Mismatches using Function Inversion
Jackson Bibbens, Levi Borevitz, and Samuel McCauley
(University of Massachusetts at Amherst, USA; Northwestern University, USA; Williams College, USA)
A classic data structure problem is to preprocess a string T of length n so that, given a query q, we can quickly find all substrings of T with Hamming distance at most k from the query string. Variants of this problem have seen significant research both in theory and in practice. For a wide parameter range, the best worst-case bounds are achieved by the “CGL tree” (Cole, Gottlieb, Lewenstein 2004), which achieves query time roughly Õ(|q| + log^k n + # occ), where # occ is the size of the output, and space O(nlog^k n). The CGL Tree space was recently improved to O(n log^k−1 n) (Kociumaka, Radoszewski 2026).
A natural question that arises is whether a high space bound is necessary. How efficient can we make queries when the data structure is constrained to O(n) space? While this question has seen extensive research, all known results have query time with unfavorable dependence on the alphabet size, n and k. The state of the art query time from (Chan, Lam, Sung, Tam, Wong 2011) is roughly Õ(|q| + |Σ|^k log^{k2 + k} n + # occ) for alphabet Σ.
We give an O(n)-space data structure with query time roughly Õ(|q| + log^4k n + log^2k n · # occ), with no dependence on the size of the alphabet. Even for a constant-sized alphabet, this is the best known query time for linear space if k≥ 3 unless # occ is large. Our results give a smooth tradeoff between time and space. Interestingly, our results are the first to extend to the sublinear space regime: we give a succinct data structure using only o(n) space in addition to the text itself, with only a modest increase in query time.
The main technical idea behind this result is to apply Fiat-Naor function inversion (Fiat, Naor 2000) to the CGL tree. Combining these techniques is not immediate; in fact, we revisit the exposition of both the Fiat-Naor data structure and the CGL tree to obtain our bounds. Along the way, we obtain improved performance for both data structures, which may be of independent interest.

@InProceedings{STOC26p1061, author = {Jackson Bibbens and Levi Borevitz and Samuel McCauley}, title = {Space-Efficient Text Indexing with Mismatches using Function Inversion}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1061-1072}, doi = {10.1145/3798129.3800818}, year = {2026}, } Publisher's Version Article: stoc26main-p480-p doi:10.1145/3798129.3800818

On the Computational Hardness of Transformers
Barna Saha, Yinzhan Xu, Christopher Ye, and Hantao Yu
(University of California at San Diego, USA; Columbia University, USA)
The transformer architecture has revolutionized modern AI across language, vision, and beyond. It consists of L layers of multi-head attention, where each layer runs H attention heads in parallel and feeds the combined output to the subsequent layer. In attention, each token within an input of length N is represented by an embedding vector of dimension m. Computationally, an attention mechanism primarily involves multiplying three N × m matrices, while applying a softmax operation to the intermediate product of the first two matrices. A significant body of work has been devoted to analyzing the time complexity of attention, leading to several recent advances.
On the other hand, known algorithms for transformers compute each attention head independently. This raises a fundamental question that has recurred throughout theoretical computer science under the guise of “direct sum” problems: can multiple instances of the same problem be solved more efficiently than solving each instance separately? Many answers to this question, both positive and negative, have arisen in fields spanning communication complexity and algorithm design. Thus, a key challenge in understanding the computational hardness of transformers is to determine whether their computation can be performed more efficiently than LH independent evaluations of attention.
In this paper, we resolve this question in the negative, and give the first non-trivial computational lower bounds for multi-head multi-layer transformers. In the small embedding regime (m = N^o(1)), computing LH attention heads separately takes LHN^{2 + o(1)} time. We establish that this is essentially optimal under the Strong Exponential Time Hypothesis (SETH). In the large embedding regime (m = N), one can compute LH attention heads separately using LHN^{ω + o(1)} arithmetic operations (plus exponents), where ω is the matrix multiplication exponent. We establish that this is optimal, by showing that LHN^{ω − o(1)} arithmetic operations are necessary when ω > 2. Our lower bound in the large embedding regime relies on a novel application of the Baur-Strassen theorem, a powerful algorithmic tool underpinning the famous backpropagation algorithm.

@InProceedings{STOC26p1073, author = {Barna Saha and Yinzhan Xu and Christopher Ye and Hantao Yu}, title = {On the Computational Hardness of Transformers}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1073-1084}, doi = {10.1145/3798129.3800819}, year = {2026}, } Publisher's Version Article: stoc26main-p482-p doi:10.1145/3798129.3800819

Quantum Precomputation: Parallelizing Cascade Circuits and the Moore–Nilsson Conjecture Is False
Adam Bene Watts, Charles R. Chen, J. William Helton, and Joseph Slote
(University of Calgary, Canada; University of California at San Diego, USA; University of Washington, USA)
Parallelization is a major challenge in quantum algorithms due to physical constraints like no-cloning. This is vividly illustrated by the conjecture of Moore and Nilsson from their seminal work on quantum circuit complexity: unitaries of a deceptively simple form—controlled-unitary “staircases”—require circuits of minimum depth Ω(n). If true, this lower bound would represent a significant break from classical parallelism and prove a quantum-native analogue of the famous NC≠ P conjecture.
In this work we settle the Moore–Nilsson conjecture in the negative by compressing all circuits in the class to depth O(logn), which is the best possible. The parallelizations are exact, ancilla-free, and can be computed in poly(n) time. We also consider circuits restricted to 2D connectivity, for which we derive compressions of optimal depth O(√n).
More generally, we make progress on the project of quantum parallelization by introducing a quantum blockwise precomputation technique somewhat analogous to the method of Arlazarov, Dinič, Kronrod, and Faradžev in classical dynamic programming, often called the “Four-Russians method.” We apply this technique to more-general “cascade” circuits as well, obtaining for example polynomial depth reductions for staircases of controlled log(n)-qubit unitaries.

@InProceedings{STOC26p1085, author = {Adam Bene Watts and Charles R. Chen and J. William Helton and Joseph Slote}, title = {Quantum Precomputation: Parallelizing Cascade Circuits and the Moore–Nilsson Conjecture Is False}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1085-1091}, doi = {10.1145/3798129.3800820}, year = {2026}, } Publisher's Version Article: stoc26main-p487-p doi:10.1145/3798129.3800820

Ideals, Macaulay Bases, and PCPs
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, and Sophus Valentin Willumsgaard
(Harvard University, USA; University of Copenhagen, Denmark)
All known proofs of the PCP theorem rely on multiple ”composition” steps, where PCPs over large alphabets are turned into PCPs over much smaller alphabets at a (relatively) small price in the soundness error of the PCP. Algebraic proofs, starting with the work of Arora, Lund, Motwani, Sudan, and Szegedy use at least 2 such composition steps, whereas the ”Gap amplification” proof of Dinur uses Θ(logn) such composition steps. In this work, we present the first PCP construction using just one composition step. The key ingredient, missing in previous work and finally supplied in this paper, is a basic PCP (of Proximity) of size 2^nε, for any ε > 0, that makes O_ε(1) queries.
At the core of our new construction is a new class of alternatives to ”sum-check” protocols. As used in past PCPs, these provide a method by which to verify that an m-variate degree d polynomial P evaluates to zero at every point of some set S ⊆ F_q^m. Previous works had shown how to check this condition for sets of the form S = H^m using O(m) queries with alphabet F_q^d assuming d ≥ |H|. Our work improves this basic protocol in two ways: First we extend it to broader classes of sets S (ones closer to Hamming balls rather than cubes). Second, it reduces the number of queries from O(m) to an absolute constant for the settings of S we consider. Specifically when S = ({0,1}_{≤ 1}^m/c)^c, where T = {0,1}_{≤ b}^a ⊆ F_q^a denotes the set of Boolean vectors of Hamming weight at most b in F_q^a, we give such an alternate to the sum-check protocol with O(1) queries with alphabet F_q^O(c+d), using proofs of size q^O(m2/c). Our new protocols use the notion of Macaulay bases to extend previously known protocols to these new settings with surprising ease. In doing so, they highlight why these notions from algebra may be of further use in complexity theory.

@InProceedings{STOC26p1092, author = {Prashanth Amireddy and Amik Raj Behera and Srikanth Srinivasan and Madhu Sudan and Sophus Valentin Willumsgaard}, title = {Ideals, Macaulay Bases, and PCPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1092-1103}, doi = {10.1145/3798129.3800821}, year = {2026}, } Publisher's Version Article: stoc26main-p505-p doi:10.1145/3798129.3800821

Memory Reallocation with Polylogarithmic Overhead
Ce Jin
(University of California at Berkeley, USA)
The Memory Reallocation problem asks to dynamically maintain an assignment of given objects of various sizes to non-overlapping contiguous chunks of memory, while supporting updates (insertions/deletions) in an online fashion. The total size of live objects at any time is guaranteed to be at most a 1−є fraction of the total memory. To handle an online update, the allocator may rearrange the objects in memory to make space, and the overhead for this update is defined as the total size of moved objects divided by the size of the object being inserted/deleted.
Our main result is an allocator with worst-case expected overhead polylog(є⁻¹). This exponentially improves the previous worst-case expected overhead O(є^−1/2) achieved by Farach-Colton, Kuszmaul, Sheffield, and Westover (2024), narrowing the gap towards the Ω(logє⁻¹) lower bound. Our improvement is based on an application of the sunflower lemma previously used by Erdős and Sárközy (1992) in the context of subset sums.
Our allocator achieves polylogarithmic overhead only in expectation, and sometimes performs expensive rebuilds. Our second technical result shows that this is necessary: it is impossible to achieve subpolynomial overhead with high probability.

@InProceedings{STOC26p1104, author = {Ce Jin}, title = {Memory Reallocation with Polylogarithmic Overhead}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1104-1115}, doi = {10.1145/3798129.3800822}, year = {2026}, } Publisher's Version Article: stoc26main-p510-p doi:10.1145/3798129.3800822

Greedy Open Addressing Revisited: Beyond Yao’s Lower Bound
Martín Farach-Colton, Andrew Krapivin, and William Kuszmaul
(New York University, USA; Carnegie Mellon University, USA)
In a widely-cited 1985 result, Yao showed that any greedy open-addressed hash table, when filled to 1 − є full, must incur an amortized expected query time of at least Ω(logє⁻¹). To overcome this lower bound, prior work has focused on modifying the setup of the insertion algorithm, by either reordering items or placing items non-greedily. We show that, in fact, no such modifications are necessary: by simply decoupling the greedy query algorithm from the greedy insertion algorithm, it is possible to get an amortized expected query time of O(1). The same relaxation also lets us bypass a barrier for worst-case expected query time, bringing the bound down to O(logє⁻¹). Finally, we show how to achieve both of these query bounds while also achieving near-optimal insertion times, for both solutions that do and solutions that do not know the parameter є beforehand.

@InProceedings{STOC26p1116, author = {Martín Farach-Colton and Andrew Krapivin and William Kuszmaul}, title = {Greedy Open Addressing Revisited: Beyond Yao’s Lower Bound}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1116-1127}, doi = {10.1145/3798129.3800823}, year = {2026}, } Publisher's Version Article: stoc26main-p516-p doi:10.1145/3798129.3800823

Monotone Circuit Complexity of Matching
Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov
(University of Oxford, UK; EPFL, Switzerland; Université de Montréal, Canada)
We show that the perfect matching function on n-vertex graphs requires monotone circuits of size 2^nΩ(1). This improves on the n^Ω(logn) lower bound of Razborov (1985). Our proof uses the standard approximation method together with a new sunflower lemma for matchings.

@InProceedings{STOC26p1128, author = {Bruno Cavalar and Mika Göös and Artur Riazanov and Anastasia Sofronova and Dmitry Sokolov}, title = {Monotone Circuit Complexity of Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1128-1132}, doi = {10.1145/3798129.3800824}, year = {2026}, } Publisher's Version Info Article: stoc26main-p518-p doi:10.1145/3798129.3800824

Constructive Approximation under Carleman’s Condition, with Applications to Smoothed Analysis
Frederic Koehler and Beining Wu
(University of Chicago, USA)
A classical consequence of Carleman’s condition is that polynomials are dense in L²(µ), but qualitative density does not quantify the degree needed for approximation over general noncompact measures. We give a basis-free Fourier-analytic framework in which orthogonality of the degree-D residual forces a zero of order D in its transformed residual, and analyticity of the moment generating function turns that zero into explicit approximation rates. In the two regimes used in this proceedings version, this yields superexponential low-frequency decay under strictly sub-exponential inputs and tanh(cΩ)^D decay under sub-exponential inputs. These two formulas are concrete special cases of a broader quantitative Denjoy–Carleman principle under Carleman’s condition, whose full logarithmic-integral form is deferred to the full version. As an application, we show that Gaussian smoothing, intrinsic-dimension reduction, and low-degree polynomial regression together give low-degree approximation guarantees for smoothed low-intrinsic-dimensional targets. This lets us solve the sub-exponential case of smoothed agnostic learning left open by Chandrasekaran, Klivans, Kontonis, Meka, and Stavropoulos, while removing the Gaussian surface area assumption in the strictly sub-exponential setting.

@InProceedings{STOC26p1133, author = {Frederic Koehler and Beining Wu}, title = {Constructive Approximation under Carleman’s Condition, with Applications to Smoothed Analysis}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1133-1144}, doi = {10.1145/3798129.3800825}, year = {2026}, } Publisher's Version Article: stoc26main-p521-p doi:10.1145/3798129.3800825

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
Debajyoti Kar, Arindam Khan, and Andreas Wiese
(IISc Bengaluru, India; TU Munich, Germany)
We study the two-dimensional (geometric) knapsack problem with rotations (2DKR), in which we are given a square knapsack and a set of rectangles with associated profits. The objective is to find a maximum profit subset of rectangles that can be packed without overlap in an axis-aligned manner, possibly by rotating some rectangles by 90^∘. The best-known polynomial time algorithm for the problem has an approximation ratio of 3/2+є for any constant є>0, with an improvement to 4/3+є in the cardinality case, due to Gálvez, Grandoni, Heydrich, Ingala, Khan, and Wiese (FOCS 2017, TALG 2021). Obtaining a PTAS for the problem, even in the cardinality case, has remained a major open question in the setting of multidimensional packing problems, as mentioned in the survey by Christensen, Khan, Tetali, and Pokutta (Computer Science Review, 2017).
In this paper, we present a PTAS for the cardinality case of 2DKR. In contrast to the setting without rotations, we show that there are (1+є)-approximate solutions in which all items are packed greedily inside a constant number of rectangular containers. Our result is based on a new resource contraction lemma, which might be of independent interest. With our techniques, we also obtain a (1+є)-approximation algorithm in the weighted case when all given items are skewed, i.e., each of them has sufficiently small height or sufficiently small width. In contrast, for the general weighted case, we prove that this simple type of packing is not sufficient to obtain a better approximation ratio than 1.5. However, we break this structural barrier and design a (1.497+є)-approximation algorithm for 2DKR in the weighted case. Our arguments also improve the best-known approximation ratio for the (weighted) case without rotations to 13/7+є ≈ 1.857+є.
Finally, we establish a lower bound of n^Ω(1/є) on the running time of any (1+є)-approximation algorithm for our problem with or without rotations – even in the cardinality setting, assuming the k-Sum Conjecture. In particular, this shows that an approximation scheme for the case of rectangles of two-dimensional geometric knapsack requires much more running time than for the case of squares.

@InProceedings{STOC26p1145, author = {Debajyoti Kar and Arindam Khan and Andreas Wiese}, title = {Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1145-1156}, doi = {10.1145/3798129.3800826}, year = {2026}, } Publisher's Version Article: stoc26main-p522-p doi:10.1145/3798129.3800826

On Proximity Gaps of Reed-Solomon Codes
Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, and Shubhangi Saraf
(StarkWare Industries, Israel; StarkWare Industries, Poland; University of Toronto, Canada)
This paper is about the proximity gaps phenomenon for Reed–Solomon codes. Very roughly, the proximity gaps phenomenon for a code C ⊆ F_qⁿ says that for two vectors f,g ∈ F_qⁿ, if sufficiently many linear combinations f + z · g (with z ∈ F_q) are close to C in Hamming distance, then so are both f and g, up to a proximity loss of ε^*. Determining the optimal quantitative form of proximity gaps for Reed–Solomon codes has recently become of great interest because of applications to interactive proofs and cryptography, and in particular, to scalable transparent arguments of knowledge (STARKs) and other modern hash based argument systems used on blockchains today.
Our main results show improved positive and negative results for proximity gaps for Reed–Solomon codes of constant relative distance δ ∈ (0,1).
(1) For proximity gaps up to the unique decoding radius δ/2, we show that arbitrarily small proximity loss ε^* > 0 can be achieved with only O_ε^*(1) exceptional z’s (improving the previous bound of O(n) exceptions).
(2) For proximity gaps up to the Johnson radius J(δ), we show that proximity loss ε^* = 0 can be achieved with only O(n) exceptional z’s (improving the previous bound of O(n²) exceptions). This significantly reduces the soundness error in the aforementioned arguments systems.
In the other direction, we show:
(1) for some Reed–Solomon codes and some δ, proximity gaps at or beyond the Johnson radius J(δ) with arbitrarily small proximity loss ε^* needs to have at least Ω(n^1.99) exceptional z’s.
(2) More generally, for all constants τ, we show that for some Reed–Solomon codes and some δ = δ(τ), proximity gaps at radius δ − Ω_τ(1) with arbitrarily small proximity loss ε^* needs to have n^τ exceptional z’s.
(3)Finally, for all Reed–Solomon codes, we show that improved proximity gaps imply improved bounds for their list-decodability. This shows that improved bounds on the list-decoding radius of Reed–Solomon codes is a prerequisite for any new proximity gaps results beyond the Johnson radius.

@InProceedings{STOC26p1157, author = {Eli Ben-Sasson and Dan Carmon and Ulrich Haböck and Swastik Kopparty and Shubhangi Saraf}, title = {On Proximity Gaps of Reed-Solomon Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1157-1167}, doi = {10.1145/3798129.3800827}, year = {2026}, } Publisher's Version Article: stoc26main-p523-p doi:10.1145/3798129.3800827

Parallel Sampling via Autospeculation
Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, and Thuy-Duong Vuong
(Stanford University, USA; University of Arizona, USA; University of Chicago, USA; University of California at San Diego, USA)
We present parallel algorithms to accelerate sampling via counting in two settings: any-order autoregressive models and denoising diffusion models. An any-order autoregressive model accesses a target distribution µ on [q]ⁿ through an oracle that provides conditional marginals, while a denoising diffusion model accesses a target distribution µ on ℝⁿ through an oracle that provides conditional means under Gaussian noise. Standard sequential sampling algorithms require Õ(n) time to produce a sample from µ in either setting. We show that, by issuing oracle calls in parallel, the expected sampling time can be reduced to Õ(n^1/2). This improves the previous Õ(n^2/3) bound for any-order autoregressive models and yields the first parallel speedup for diffusion models in the high-accuracy regime, under the relatively mild assumption that the support of µ is bounded.
We introduce a novel technique to obtain our results: speculative rejection sampling. This technique leverages an auxiliary “speculative” distribution ν that approximates µ to accelerate sampling. Our technique is inspired by the well-studied “speculative decoding” techniques popular in large language models, but differs in key ways. Firstly, we use “autospeculation,” namely we build the speculation ν out of the same oracle that defines µ. In contrast, speculative decoding typically requires a separate, faster, but potentially less accurate “draft” model ν. Secondly, the key differentiating factor in our technique is that we make and accept speculations at a “sequence” level rather than at the level of single (or a few) steps. This last fact is key to unlocking our parallel runtime of Õ(n^1/2).

@InProceedings{STOC26p1168, author = {Nima Anari and Carlo Baronio and CJ Chen and Alireza Haqi and Frederic Koehler and Anqi Li and Thuy-Duong Vuong}, title = {Parallel Sampling via Autospeculation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1168-1179}, doi = {10.1145/3798129.3800828}, year = {2026}, } Publisher's Version Article: stoc26main-p524-p doi:10.1145/3798129.3800828

Efficient Reversal of Transductions of Sparse Graph Classes
Jan Dreier, Jakub Gajarský, and Michał Pilipczuk
(TU Wien, Austria; University of Warsaw, Poland; Masaryk University, Brno, Czech Republic)
(First-order) transductions are a basic notion capturing graph modifications that can be described in first-order logic. In this work, we propose an efficient algorithmic method to approximately reverse the application of a transduction, assuming the source graph is sparse. Precisely, for any graph class C that has structurally bounded expansion (i.e., can be transduced from a class of bounded expansion), we give an O(n⁴)-time algorithm that given a graph G∈ C, computes a vertex-colored graph H such that G can be recovered from H using a first-order interpretation and H belongs to a graph class D of bounded expansion. This answers an open problem raised by Gajarský et al. [ACM TOCL, ’20]. In fact, for our procedure to work we only need to assume that C is monadically stable (i.e., does not transduce the class of all half-graphs) and has inherently linear neighborhood complexity (i.e., the neighborhood complexity is linear in all graph classes transducible from C). This renders the conclusion that the graph classes satisfying these two properties coincide with classes of structurally bounded expansion.
Our methods also yield a O(n⁴)-time algorithm that computes neighborhood covers with constant overlap for monadically stable graph classes that have inherently linear neighborhood complexity.

@InProceedings{STOC26p1180, author = {Jan Dreier and Jakub Gajarský and Michał Pilipczuk}, title = {Efficient Reversal of Transductions of Sparse Graph Classes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1180-1191}, doi = {10.1145/3798129.3800829}, year = {2026}, } Publisher's Version Article: stoc26main-p530-p doi:10.1145/3798129.3800829

Markov Chains Approximate Message Passing
Amit Rajaraman and David X. Wu
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)
Markov chain Monte Carlo algorithms have long been observed to obtain near-optimal performance in various Bayesian inference settings. However, developing a supporting theory that makes these studies rigorous has proved challenging. In this paper, we study the classical spiked Wigner inference problem, where one aims to recover a planted Boolean spike from a noisy matrix measurement. We relate the recovery performance of Glauber dynamics on the annealed posterior to the performance of Approximate Message Passing (AMP), which is known to achieve Bayes-optimal performance. Our main results rely on the analysis of an auxiliary Markov chain called restricted Gaussian dynamics (RGD). Concretely, we establish the following three results. First, RGD can be reduced to an effective one-dimensional recursion which mirrors the evolution of the AMP iterates. Second, from a warm start, RGD rapidly converges to a fixed point in correlation space, which recovers Bayes-optimal performance when run on the posterior. Third, conditioned on widely believed mixing results for the SK model, we recover the phase transition for non-trivial inference. The full version of this paper can be found on arXiv (arXiv ID: 2512.02384).

@InProceedings{STOC26p1192, author = {Amit Rajaraman and David X. Wu}, title = {Markov Chains Approximate Message Passing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1192-1199}, doi = {10.1145/3798129.3800830}, year = {2026}, } Publisher's Version Article: stoc26main-p535-p doi:10.1145/3798129.3800830

Online Combinatorial Optimization with Graphical Dependencies
Zhimeng Gao, Evangelia Gergatsouli, Kalen Patton, and Sahil Singla
(Georgia Institute of Technology, USA)
Most existing work in online stochastic combinatorial optimization assumes that inputs are drawn from independent distributions—a strong assumption that often fails in practice. At the other extreme, arbitrary correlations are equivalent to worst-case inputs via Yao’s minimax principle, making good algorithms often impossible. This motivates the study of intermediate models that capture mild correlations while still permitting nontrivial algorithms.
In this paper, we study online combinatorial optimization under Markov Random Fields (MRFs), a well-established graphical model for structured dependencies. MRFs parameterize correlation strength via the maximum weighted degree Δ, smoothly interpolating between independence (Δ = 0) and full correlation (Δ → ∞). While naively this yields e^O(Δ)-competitive algorithms and Ω(Δ) hardness, we ask: When can we design tight Θ(Δ)-competitive algorithms?
We present general techniques achieving O(Δ)-competitive algorithms for both minimization and maximization problems under MRF-distributed inputs. For minimization problems with coverage constraints (e.g., Facility Location and Steiner Tree), we reduce to the well-studied p-sample model. For maximization problems (e.g., matchings and combinatorial auctions with XOS buyers), we extend the ”balanced prices” framework for online allocation problems to MRFs.

@InProceedings{STOC26p1200, author = {Zhimeng Gao and Evangelia Gergatsouli and Kalen Patton and Sahil Singla}, title = {Online Combinatorial Optimization with Graphical Dependencies}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1200-1211}, doi = {10.1145/3798129.3800831}, year = {2026}, } Publisher's Version Article: stoc26main-p545-p doi:10.1145/3798129.3800831

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time Barrier
Sayan Bhattacharya, Ermiya Farokhnejad, and Haoze Wang
(University of Warwick, UK; Peking University, China)
We consider the “minimum degree spanning tree” problem. As input, we receive an undirected, connected graph G=(V, E) with n nodes and m edges, and our task is to find a spanning tree T of G that minimizes max_{u ∈ V} deg_T(u), where deg_T(u) denotes the degree of u ∈ V in T.
The problem is known to be NP-hard. In the early 1990s, an influential work by Fürer and Raghavachari presented a local search algorithm that runs in Õ(mn) time, and returns a spanning tree with maximum degree at most Δ^⋆+1, where Δ^⋆ is the optimal objective. This remained the state-of-the-art runtime bound for computing an additive one approximation, until now.
We break this O(mn) runtime barrier dating back to three decades, by providing a deterministic algorithm that returns an additive one approximate optimal spanning tree in Õ(mn^3/4) time. This constitutes a substantive progress towards answering an open question that has been repeatedly posed in the literature [Pettie’2016, Duan and Pettie’2020, Saranurak’2024].
Our algorithm is based on a novel application of the blocking flow paradigm.

@InProceedings{STOC26p1212, author = {Sayan Bhattacharya and Ermiya Farokhnejad and Haoze Wang}, title = {Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time Barrier}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1212-1223}, doi = {10.1145/3798129.3800832}, year = {2026}, } Publisher's Version Article: stoc26main-p548-p doi:10.1145/3798129.3800832

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
Slobodan Mitrović, Srikkanth Ramachandran, Ronitt Rubinfeld, and Mihir Singhal
(University of California at Davis, USA; University of Novi Sad, Serbia; Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)
In this work, we focus on designing an efficient Local Computation Algorithm (LCA) for the set cover problem, which is a core optimization task. The state-of-the-art LCA for computing O(logΔ)-approximate set cover, developed by Grunau, Mitrović, Rubinfeld, and Vakilian [SODA ’20], achieves query complexity of Δ^O(logΔ) · f^{O(logΔ · (loglogΔ + loglogf))}, where Δ is the maximum set size, and f is the maximum frequency of any element in sets. We present a new LCA that solves this problem using f^O(logΔ) queries. Specifically, for instances where f = poly logΔ, our algorithm improves the query complexity from Δ^O(logΔ) to Δ^O(loglogΔ).
Our central technical contribution in designing LCAs is to aggressively sparsify the input instance to allow for retroactive updates. Namely, our main LCA sometimes “corrects” decisions it made in the previous recursive LCA calls. It enables us to achieve stronger concentration guarantees, which in turn allows for more efficient and “sparser” LCA execution. We believe that this technique will be of independent interest.

@InProceedings{STOC26p1224, author = {Slobodan Mitrović and Srikkanth Ramachandran and Ronitt Rubinfeld and Mihir Singhal}, title = {Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1224-1235}, doi = {10.1145/3798129.3800833}, year = {2026}, } Publisher's Version Article: stoc26main-p551-p doi:10.1145/3798129.3800833

Mixing of General Biased Adjacent Transposition Chains
Reza Gheissari, Holden Lee, and Eric Vigoda
(Northwestern University, USA; Johns Hopkins University, USA; University of California at Santa Barbara, USA)
We analyze the general biased adjacent transposition shuffle process, which is a well-studied Markov chain on the symmetric group S_n. In each step, an adjacent pair of elements i and j are chosen, and then i is placed ahead of j with probability p_ij. This Markov chain arises in the study of self-organizing lists in theoretical computer science, and has close connections to exclusion processes from statistical physics and probability theory. It is conjectured (see Fill (2003)) that for general p_ij satisfying p_ij ≥ 1/2 for all i<j and a simple monotonicity condition, the mixing time is polynomial. We prove that for any fixed ε>0, as long as p_ij >1/2+ε for all i<j, the mixing time is Θ(n²) and exhibits pre-cutoff. Our key technical result is a form of spatial mixing for the general biased transposition chain after a suitable burn-in period. In order to use this for a mixing time bound, we adapt multiscale arguments for mixing times from the setting of spin systems to the symmetric group.

@InProceedings{STOC26p1236, author = {Reza Gheissari and Holden Lee and Eric Vigoda}, title = {Mixing of General Biased Adjacent Transposition Chains}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1236-1241}, doi = {10.1145/3798129.3800834}, year = {2026}, } Publisher's Version Article: stoc26main-p565-p doi:10.1145/3798129.3800834

Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
Aviad Rubinstein and Sahil Singla
(Stanford University, USA; Georgia Institute of Technology, USA)
We revisit three fundamental problems in algorithms under uncertainty: the Secretary Problem, Prophet Inequality, and Stochastic Probing, each subject to general downward-closed constraints. When elements have binary values, all three problems admit a tight Θ(logn)-factor approximation guarantee. For general (non-binary) values, however, the best known algorithms lose an additional logn factor when discretizing to binary values, leaving a quadratic gap of Θ(logn) vs. Θ(log² n).
We resolve this quadratic gap for all three problems, showing Ω(log² n)-hardness for two of them and an O(logn)-approximation algorithm for the third. While the technical details differ across settings, and between algorithmic and hardness proofs, all our results stem from a single core observation, which we call the Big-Decisions-First Principle: Under uncertainty, it is better to resolve high-stakes (large-value) decisions early.

@InProceedings{STOC26p1242, author = {Aviad Rubinstein and Sahil Singla}, title = {Secretary, Prophet, and Stochastic Probing via Big-Decisions-First}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1242-1253}, doi = {10.1145/3798129.3800835}, year = {2026}, } Publisher's Version Article: stoc26main-p569-p doi:10.1145/3798129.3800835

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
Yotam Kenneth-Mordoch and Robert Krauthgamer
(Weizmann Institute of Science, Israel)
All-Pairs Minimum Cut (APMC) is a fundamental graph problem that asks to find a minimum s,t-cut for every pair of vertices s,t. A recent line of work on fast algorithms for APMC has culminated with a reduction of APMC to polylog(n)-many max-flow computations. But unfortunately, no fast algorithms are currently known for exact max-flow in several standard models of computation, such as the cut-query model and the fully-dynamic model.
Our main technical contribution is a sparsifier that preserves all minimum s,t-cuts in an unweighted graph, and can be constructed using only approximate max-flow computations. We then use this sparsifier to devise new algorithms for APMC in unweighted graphs in several computational models: (i) a randomized algorithm that makes Õ(n^3/2) cut queries to the input graph; (ii) a deterministic fully-dynamic algorithm with n^3/2+o(1) worst-case update time; and (iii) a randomized two-pass streaming algorithm with space requirement Õ(n^3/2). These results improve over the known bounds, even for (single pair) minimum s,t-cut in the respective models.

@InProceedings{STOC26p1254, author = {Yotam Kenneth-Mordoch and Robert Krauthgamer}, title = {Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1254-1265}, doi = {10.1145/3798129.3800836}, year = {2026}, } Publisher's Version Article: stoc26main-p571-p doi:10.1145/3798129.3800836

The Debiased Keyl’s Algorithm: A New Unbiased Estimator for Full State Tomography
Angelos Pelecanos, Jack Spilecki, and John Wright
(University of California at Berkeley, USA)
In the problem of quantum state tomography, one is given n copies of an unknown rank-r mixed state ρ ∈ ℂ^{d × d} and asked to produce an estimator of ρ. In this work, we present the debiased Keyl’s algorithm, the first estimator for full state tomography which is both unbiased and sample-optimal. We derive an explicit formula for the second moment of our estimator, with which we show the following five applications. First, we give a new proof that n = O(rd/ε²) copies are sufficient to learn a rank-r mixed state to trace distance error ε, which is optimal. Second, we show that n = O(rd/ε²) copies are sufficient to learn to error ε in the more challenging Bures distance, which is also optimal. Third, we consider full state tomography when one is only allowed to measure k copies at once. We show that n =O(max(d³/√kε², d²/ε² ) ) copies suffice to learn in trace distance. This improves on the prior work of Chen et al. and matches their lower bound. Fourth, for shadow tomography, we show that O(log(m)/ε²) copies are sufficient to learn m given observables O₁, …, O_m in the ”high accuracy regime”, when ε = O(1/d), improving on a result of Chen et al. More generally, we show that if tr(O_i²) ≤ F for all i, then n = O(log(m) · (min{√r F/ε, F^2/3/ε^4/3}+ 1/ε²)) copies suffice, improving on existing work. Finally, for quantum metrology, we give a locally unbiased algorithm whose mean squared error matrix is upper bounded by twice the inverse of the quantum Fisher information matrix in the asymptotic limit of large n, which is optimal.

@InProceedings{STOC26p1266, author = {Angelos Pelecanos and Jack Spilecki and John Wright}, title = {The Debiased Keyl’s Algorithm: A New Unbiased Estimator for Full State Tomography}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1266-1277}, doi = {10.1145/3798129.3800837}, year = {2026}, } Publisher's Version Article: stoc26main-p589-p doi:10.1145/3798129.3800837

Hardness Amplification beyond Boolean Functions
Nobutaka Shimizu and Kenji Yasunaga
(Institute of Science Tokyo, Japan)
A central goal in average-case complexity is to understand how average-case hardness can be amplified to near-optimal hardness. Classical results such as Yao’s XOR lemma establish this principle for Boolean functions, but these techniques typically apply only to artificially constructed functions, rather than to natural computational problems. In this work, we extend hardness amplification beyond the Boolean setting and extend the XOR Lemma to the sum of functions over the finite field F_p, where p is a prime. Specifically, we show that if a function f ∶ {0,1}ⁿ → F_p fails to be computed on at least a δ-fraction of inputs, then the k-wise sum f^+k(x₁,…,x_k) = f(x₁) + ⋯ + f(x_k) becomes almost optimally unpredictable: no efficient algorithm can compute it with success probability exceeding 1 + ε/p for suitable parameters k,δ,ε. Our proof is based on the pseudo-average-min entropy characterization of unpredictability due to Zheng (2014) and Vadhan and Zheng (2012), which we simplify and quantitatively refine to make the dependence of the circuit blow-up on all parameters fully explicit.
As an application, we obtain the first error-tolerant random self-reduction for a natural subgraph counting problem. Specifically, we show that any circuit that correctly counts triangles in an Erdős-Rényi random graph with noticeable probability can be transformed into a worst-case circuit with only a quasi-linear overhead.
We further extend the query lower bound framework of Shaltiel and Viola (2010) to the F_p-valued setting, proving that any (possibly adaptive) black-box hardness amplification over F_p must make at least Ω(plog(1/δ)/ε²) oracle queries. Our proof substantially simplifies the core fixed-set lemma underlying previous analyses, offering a more modular and entropy-based argument.

@InProceedings{STOC26p1278, author = {Nobutaka Shimizu and Kenji Yasunaga}, title = {Hardness Amplification beyond Boolean Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1278-1289}, doi = {10.1145/3798129.3800838}, year = {2026}, } Publisher's Version Article: stoc26main-p590-p doi:10.1145/3798129.3800838

Compressing Dynamic Fully Indexable Dictionaries in Word-RAM
Gabriel Marques Domingues
(Tel Aviv University, Israel)
We study the problem of constructing a dynamic fully indexable dictionary (FID) in the Word-RAM model using space close to the information-theoretic lower bound. A FID is a data-structure that encodes a bit-vector B of length u and answers, for b∈{0,1}, rank_b(B, x)=|{y≤ x | B[y]=b}| and select_b(B, r)=min{0≤ x<u | rank_b(B, x)=r} (−1 if empty). A dynamic FID supports updates that modify a single bit of B, i.e., B[i]← b.
We work in the Word-RAM model with w-bit words, assuming w≥ lg u. Integer multiplication takes O(1) time. Our memory model is M_B, allowing access to a fixed precomputed table of τ=polylog(w) words, which can be computed in O(wτ) time.
In this paper, we show a dynamic FID based on the famous fusion-tree data-structure of Pătraşcu and Thorup [FOCS 2014], modified to use fewer bits and to support select₀. Let n denote the number of ones in B. We describe a parametric construction: for every є≤ 1/2, there is a dynamic FID using
lg⎛ ⎜ ⎝un
⎞ ⎟ ⎠
+O(nw^є/є) bits
taking O(1/є+log_w(n)) time for rank₀/rank₁/select₀ and updates, and O(log_w(n)) time for select₁. All time bounds are worst-case. For є=1/√lg w, we reduce the space to lg(
un
)+O(nlogw) bits. For є=Θ(1), the running time matches the lower bound of Fredman and Saks [STOC 1989]. For є=1/4, this is the first deterministic dynamic FID using multiplication that achieves o(n√w) bits of redundancy in M_B, and optimal worst-case time.

@InProceedings{STOC26p1290, author = {Gabriel Marques Domingues}, title = {Compressing Dynamic Fully Indexable Dictionaries in Word-RAM}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1290-1301}, doi = {10.1145/3798129.3800839}, year = {2026}, } Publisher's Version Article: stoc26main-p594-p doi:10.1145/3798129.3800839

The Price of Competitive Information Disclosure
Siddhartha Banerjee, Kamesh Munagala, Yiheng Shen, and Kangning Wang
(Cornell University, USA; Duke University, USA; Rutgers University, USA)
In many decision-making scenarios, individuals strategically choose what information to disclose to optimize their own outcomes. It is unclear whether such strategic information disclosure can lead to good societal outcomes. To address this question, we consider a competitive Bayesian persuasion model in which multiple agents selectively disclose information about their qualities to a principal, who aims to choose the candidates with the highest qualities. Using the price-of-anarchy framework, we quantify the inefficiency of such strategic disclosure. We show that the price of anarchy is at most a constant when the agents have independent quality distributions, even if their utility functions are heterogeneous. This result provides the first theoretical guarantee on the limits of inefficiency in Bayesian persuasion with competitive information disclosure.

@InProceedings{STOC26p1302, author = {Siddhartha Banerjee and Kamesh Munagala and Yiheng Shen and Kangning Wang}, title = {The Price of Competitive Information Disclosure}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1302-1313}, doi = {10.1145/3798129.3800840}, year = {2026}, } Publisher's Version Article: stoc26main-p601-p doi:10.1145/3798129.3800840

Beating Meet-in-the-Middle for Subset Balancing Problems
Tim Randolph and Karol Węgrzycki
(Harvey Mudd College, USA; MPI-INF, Germany)
We consider exact algorithms for Subset Balancing, a family of related problems that generalizes Subset Sum, Partition, and Equal Subset Sum. Specifically, given as input an integer vector x^→ ∈ ℤⁿ and a constant-size coefficient set C ⊂ ℤ, we seek a nonzero solution vector c^→ ∈ Cⁿ satisfying c^→ · x^→ = 0.
For C = {−d,…,d}, d > 1 and C = {−d,…,d}∖{0}, d > 2, we present algorithms that run in time O(|C|^{(0.5 − є)n}) for a constant є > 0 that depends only on C. This improves on the result of Chen, Jin, Randolph and Servedio (SODA 2022), who broke the Meet-in-the-Middle barrier on these coefficient sets in the average-case setting. We also improve the best exact algorithm for Equal Subset Sum (Subset Balancing with C = {−1,0,1}), due to Mucha, Nederlof, Pawlewicz, and Węgrzycki (ESA 2019), by an exponential margin. This positively answers an open question of Jin, Williams, and Zhang (ESA 2025). Our results leave two natural cases in which we cannot yet break the Meet-in-the-Middle barrier: C = {−2, −1, 1, 2} and C = {−1, 1} (Partition).
Our results bring the representation technique of Howgrave-Graham and Joux (CRYPTO 2010) from average-case to worst-case inputs for many C. This requires a variety of new techniques: we present strategies for (1) achieving good “mixing” with worst-case inputs, (2) creating flexible input representations for coefficient sets without 0, and (3) quickly recovering compatible solution pairs from sets of vectors containing “pseudosolution pairs”.

@InProceedings{STOC26p1314, author = {Tim Randolph and Karol Węgrzycki}, title = {Beating Meet-in-the-Middle for Subset Balancing Problems}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1314-1325}, doi = {10.1145/3798129.3800841}, year = {2026}, } Publisher's Version Article: stoc26main-p606-p doi:10.1145/3798129.3800841

A Theory for Probabilistic Polynomial-Time Reasoning
Lijie Chen, Jiatu Li, Igor C. Oliveira, and Ryan Williams
(University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; University of Warwick, UK)
In this work, we propose a new bounded arithmetic theory, denoted APX₁, designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer science. Under plausible assumptions, APX₁ is strictly weaker than previously proposed frameworks, such as the theory APC₁ introduced in the seminal work of Jeřábek (2007). From a computational standpoint, APX₁ is closely tied to approximate counting and to the central question in derandomization, the prBPP versus prP problem, whereas APC₁ is linked to the dual weak pigeonhole principle and to the existence of Boolean functions with exponential circuit complexity.
A key motivation for introducing APX₁ is that its weaker axioms expose finer proof-theoretic structure, making it a natural setting for several lines of research, including unprovability of complexity conjectures and reverse mathematics of randomized lower bounds. In particular, the framework we develop for APX₁ enables the formulation of precise questions concerning the provability of prBPP = prP in deterministic feasible mathematics. Since the (un)provability of P versus NP in bounded arithmetic has long served as a central theme in the field, we expect this line of investigation to be of particular interest.
Our technical contributions include developing a comprehensive foundation for probabilistic reasoning from weaker axioms, formalizing non-trivial results from theoretical computer science in APX₁, and establishing a tailored witnessing theorem for its provably total TFNP problems. As a byproduct of our analysis of the minimal proof-theoretic strength required to formalize statements arising in theoretical computer science, we resolve an open problem regarding the provability of AC⁰ lower bounds in PV₁, which was considered in earlier works by Razborov (1995), Krajíček (1995), and Müller and Pich (2020).

@InProceedings{STOC26p1326, author = {Lijie Chen and Jiatu Li and Igor C. Oliveira and Ryan Williams}, title = {A Theory for Probabilistic Polynomial-Time Reasoning}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1326-1337}, doi = {10.1145/3798129.3800842}, year = {2026}, } Publisher's Version Article: stoc26main-p624-p doi:10.1145/3798129.3800842

The Natural Proofs Barrier against Data-Structure Lower-Bounds
Michal Koucký, Bruno Loff, Tulasimohan Molli, and Michael E. Saks
(Charles University, Czech Republic; LASIGE, Portugal; University of Lisbon, Portugal; BITS Pilani, India; Unaffiliated, USA)
Consider a data structure problem with possible data coming from a set D, queries coming from a set Q, and in the dynamic case updates coming from a set U. Then, the current state of the art in data structure lower bounds is t = Ω(log|Q|) for static data structure problems, and max(t_q,t_u) = Ω((logn)²) where n = max(|Q|,|U|,log|D|) for dynamic. We port Razborov and Rudich’s natural-proofs framework to the setting of static and dynamic data structures in the cell probe model, in a way that strongly suggests this state of the art is unlikely to be improved anytime soon. A similar direction was recently taken also by Korten, Pitassi and Impagliazzo (FOCS 2025) who look at static data structure lower bounds in a different regime of parameters. Our contribution is: We define notions analogous to pseudo-random functions (PRF). We call these primitives local PRFs, in the context of static data structures, and local and locally updatable (LLU) PRFs, in the context of dynamic data structures. We then formulate cryptographic conjectures, namely, that secure local PRFs and secure LLU PRFs exist, precisely at the frontier where we are no longer able to prove static, respectively dynamic, data structure lower bounds. If these conjectures are true, it follows that the current state of the art in data structure lower bounds cannot be improved by a natural proof. We show that (almost) every single known data structure lower bound proof is a natural proof, by surveying all lower bounds in the literature known to us. (The only exception is proofs based on lifting theorems.) It follows that, if our cryptographic conjecture is true, then all known lower bound proof techniques (minus the one exception) are unable to improve upon the state of the art. (We also attempt to address the exception.) Further, we provide concrete candidate constructions for our two pseudo-random primitives. We conjecture that our constructions are secure for parameters just above the state-of-the-art lower bounds. We also show that, whether or not they are secure, our candidate PRFs at least satisfy the natural properties appearing in all (but one) known proofs. So if one is interested in improving upon the state of the art in static or dynamic data structure lower bounds, one must either find a non-natural method of proving such lower bounds (no such method currently exists), or one may as well begin by trying to break our PRF candidates.

@InProceedings{STOC26p1338, author = {Michal Koucký and Bruno Loff and Tulasimohan Molli and Michael E. Saks}, title = {The Natural Proofs Barrier against Data-Structure Lower-Bounds}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1338-1343}, doi = {10.1145/3798129.3800843}, year = {2026}, } Publisher's Version Info Article: stoc26main-p628-p doi:10.1145/3798129.3800843

Extractors for Samplable Distributions from the Two-Source Extractor Recipe
Justin Oh and Ronen Shaltiel
(University of Haifa, Israel)
Seedless extractors for samplable distributions were first constructed under a very strong complexity-theoretic hardness assumption: that E=DTIME(2^O(n)) is hard for exponential-size circuits with oracle access to a fixed level of the polynomial hierarchy. That construction applies to sources with min-entropy k=(1−γ)n for an arbitrarily small constant γ>0. Subsequent works weakened the hardness assumption and improved the min-entropy threshold to k=n^1−γ and then to k=n^Ω(1), though these improvements again relied on hardness against circuits with oracle access to the polynomial hierarchy.
We introduce a new approach to constructing extractors for samplable distributions, inspired by constructions of two-source extractors. Our approach relies on a new, incomparable hardness assumption involving only deterministic circuits, and reduces the task of constructing extractors for samplable distributions to that of constructing explicit non-malleable extractors with short seed length.
The new assumption has the same flavor as the classic assumption that E is hard for exponential-size circuits. Specifically, we assume that there exists a constant 0<α<1 such that for every constant C_hard≥ 1, there exist a constant C_easy and a problem in DTIME(2^C_easyn) that is not in DTIME(2^C_hardn)/2^{α n}. A notable feature of this assumption is that the adversary is allowed to run in time exceeding 2ⁿ, while still being restricted to fewer than 2ⁿ bits of nonuniformity.
Under this assumption, we construct an explicit extractor for samplable distributions with min-entropy k=O(logn), matching the threshold achieved by the probabilistic method. More precisely, for every constant c≥ 1 and every constant ε >0, there exists a constant c′ and an explicit extractor Ext:{0,1}ⁿ→{0,1} with error ε for distributions of min-entropy at least c′logn that are samplable by circuits of size n^c.
The key observation underlying our construction is that for a samplable source, the set of bad seeds for a non-malleable extractor is efficiently recognizable. We use this observation to show that, in the relevant two-source extractor constructions, the second source can be replaced by the truth table of a sufficiently hard function. This yields an unexpected connection between two-source extractors and extractors for samplable distributions, paralleling the classical connection between extractors and pseudorandom generators in the opposite direction.

@InProceedings{STOC26p1344, author = {Justin Oh and Ronen Shaltiel}, title = {Extractors for Samplable Distributions from the Two-Source Extractor Recipe}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1344-1352}, doi = {10.1145/3798129.3800844}, year = {2026}, } Publisher's Version Article: stoc26main-p633-p doi:10.1145/3798129.3800844

The Sample Complexity of Uniform Approximation for Multi-dimensional CDFs and Fixed-Price Mechanisms
Matteo Castiglioni, Anna Lunghi, and Alberto Marchesi
(Politecnico di Milano, Italy)
We study the sample complexity of learning a uniform approximation of an n-dimensional cumulative distribution function (CDF) within an error є > 0, when observations are restricted to a minimal one-bit feedback. This serves as a counterpart to the multivariate DKW inequality under “full feedback”, extending it to the setting of “bandit feedback”. Our main result shows a near-dimensional-invariance in the sample complexity: we get a uniform є-approximation with a sample complexity 1/є³log(1/є)^O(n) over a arbitrary fine grid, where the dimensionality n only affects logarithmic terms. As direct corollaries, we provide tight sample complexity bounds and novel regret guarantees for learning fixed-price mechanisms in small markets, such as bilateral trade settings.

@InProceedings{STOC26p1353, author = {Matteo Castiglioni and Anna Lunghi and Alberto Marchesi}, title = {The Sample Complexity of Uniform Approximation for Multi-dimensional CDFs and Fixed-Price Mechanisms}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1353-1364}, doi = {10.1145/3798129.3800845}, year = {2026}, } Publisher's Version Article: stoc26main-p634-p doi:10.1145/3798129.3800845

Lower Bounds on Flow Sparsifiers with Steiner Nodes
Yu Chen, Zihan Tan, and Mingyang Yang
(National University of Singapore, Singapore; University of Minnesota, USA)
Given a large graph G with a set of its k vertices called terminals, a quality-q flow sparsifier is a small graph G′ that contains the terminals and preserves all multicommodity flows between them up to some multiplicative factor q≥ 1, called the quality. Constructing flow sparsifiers with good quality and small size (|V(G′)|) has been a central problem in graph compression.
The most common approach of constructing flow sparsifiers is contraction: first compute a partition of the vertices in V(G), and then contract each part into a supernode to obtain G′. When G′ is only allowed to contain all terminals, the best quality is shown to be O(logk/loglogk) and Ω(√logk/loglogk).
In this paper, we show that allowing a few Steiner nodes does not help much in improving the quality. Specifically, there exist k-terminal graphs such that, even if we allow k· 2^(logk)Ω(1) Steiner nodes in its contraction-based flow sparsifier, the quality is still Ω((logk)^0.3).

@InProceedings{STOC26p1365, author = {Yu Chen and Zihan Tan and Mingyang Yang}, title = {Lower Bounds on Flow Sparsifiers with Steiner Nodes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1365-1375}, doi = {10.1145/3798129.3800846}, year = {2026}, } Publisher's Version Article: stoc26main-p636-p doi:10.1145/3798129.3800846

Approximation Does Not Help in Quantum Unitary Time-Reversal
Kean Chen, Nengkun Yu, and Zhicheng Zhang
(University of Pennsylvania, USA; Stony Brook University, USA; University of Technology Sydney, Australia)
Access to the time-reverse U⁻¹ of an unknown quantum unitary process U is widely assumed in quantum learning, metrology, and many-body physics. The fundamental task of unitary time-reversal dictates implementing U⁻¹ to within diamond-norm error є using black-box queries to the d-dimensional unitary U. Although the query complexity of this task has been extensively studied, existing lower bounds either hold only for the exact case (i.e., є=0) or are suboptimal in d. This raises a central question: does approximation help reduce the query complexity of unitary time-reversal? We settle this question in the negative by establishing a robust and tight lower bound Ω((1−є)d²) with explicit dependence on the error є. This implies that unitary time-reversal retains optimal exponential hardness (in the number of qubits) even when constant error is allowed. Our bound applies to adaptive and coherent algorithms with unbounded ancillas and holds even when є is an average-case distance error.

@InProceedings{STOC26p1376, author = {Kean Chen and Nengkun Yu and Zhicheng Zhang}, title = {Approximation Does Not Help in Quantum Unitary Time-Reversal}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1376-1387}, doi = {10.1145/3798129.3800847}, year = {2026}, } Publisher's Version Article: stoc26main-p656-p doi:10.1145/3798129.3800847

A Graph Minors Approach to Temporal Sequences
Johannes Carmesin and Will J. Turner
(TU Bergakademie Freiberg, Germany)
We develop a structural approach to simultaneous embeddability in temporal sequences of graphs, inspired by graph minor theory. Our main result is a classification theorem for 2-connected temporal sequences: we identify five obstruction classes and show that every 2-connected temporal sequence is either simultaneously embeddable or admits a sequence of improvements leading to an obstruction. This structural insight leads to a polynomial-time algorithm for deciding the simultaneous embeddability of 2-connected temporal sequences.
The restriction to 2-connected sequences is necessary, as the problem is NP-hard for connected graphs, while trivial for 3-connected graphs. As a consequence, our framework also resolves the rooted-tree SEFE problem, a natural extension of the well-studied Sunflower SEFE.
Our results uncover a rich structural theory of temporal planarity, laying the groundwork for a temporal graph minors theory.

@InProceedings{STOC26p1388, author = {Johannes Carmesin and Will J. Turner}, title = {A Graph Minors Approach to Temporal Sequences}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1388-1396}, doi = {10.1145/3798129.3800848}, year = {2026}, } Publisher's Version Article: stoc26main-p668-p doi:10.1145/3798129.3800848

What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing
Lélia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca
(IRIF - Université Paris Cité - CNRS, France; University of Bergen, Norway; École Normale Supérieure, France; Universidad Adolfo Ibáñez, Chile; Universidad de Chile, Chile; Université d'Orléans, France)
The question of "what can be computed locally?" lies at the heart of distributed computing in networks. As established in Naor and Stockmeyer's seminal paper (STOC 1993, Edsger W. Dijkstra Prize in Distributed Computing 2025), this question is undecidable, even for graph problems whose solutions can be checked locally. In this paper, we adopt a novel perspective on the question, by asking for which classes Π of problems, and for which classes G of graphs, all problems in Π can be solved efficiently in a distributed manner in all graphs of G. This paper focuses on two natural candidates for such an approach, namely the class of problems expressible in first-order logic (FO), because they possess an intrinsic form of locality thanks to Gaifman's theorem, and the class of graphs with bounded expansion, because they form a large class of graphs encompassing, e.g., planar, bounded-genus, bounded-treewidth, and bounded-degree graphs, as well as graphs excluding a fixed minor or topological minor, sparse Erdös--Rényi graphs (a.a.s.), and several network models such as stochastic block models for suitable parameter ranges.
The starting point of our work is the decade-old open question of Nešetřil and Ossona de Mendez (Distributed Computing 2016) on the distributed complexity of local FO formulas on graphs of bounded expansion, in the standard CONGEST model of distributed computing. Recall that a formula φ(x) is local if the satisfaction of φ(x) depends only on the r-neighborhood of its free variable x, for some fixed r. For instance, the formula "x belongs to a triangle" is local. We resolve the open problem of Nešetřil and Ossona de Mendez positively by showing that, for every local FO formula φ(x), and for every graph class G of bounded expansion, there exists a deterministic algorithm that identifies, for every n-vertex graph G ∈ G, all vertices v of G such that G ⊨ φ(v), in O(log n) rounds. The requirement of locality is unavoidable, as even the simple FO formula "there exist two vertices of degree 3" requires Ω(D) rounds in CONGEST, even on trees of diameter D. Nevertheless, we establish a second result, which goes beyond the question of Nešetřil and Ossona de Mendez. We show that O(D + log n) rounds are sufficient for deciding any FO formula φ on graphs of bounded expansion. That is, the overhead to be paid over the diameter is just O(log n). We underline that the techniques behind our two distributed "meta-theorems" extend to distributed counting, optimization, and certification problems.
Our results are tight in several ways. Regarding the choice of the graph class G, we show that deciding FO formulas may have high round complexity in CONGEST on larger classes of graphs, even if they remain sparse. For instance, the simple local FO formula expressing C₆-freeness requires O~(sqrt(n)) rounds to be decided in graphs of degeneracy 2 with constant diameter. Regarding the choice of the class Π of problems, we show that deciding problems expressible in monadic second-order (MSO) logic may have high round complexity in CONGEST, even in classes of graphs with bounded expansion. For example, deciding non-3-colorability requires O~(n) rounds in bounded-degree graphs with logarithmic diameter.

@InProceedings{STOC26p1397, author = {Lélia Blin and Fedor V. Fomin and Pierre Fraigniaud and Sylvain Gay and Petr A. Golovach and Pedro Montealegre and Ivan Rapaport and Ioan Todinca}, title = {What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1397-1408}, doi = {10.1145/3798129.3800849}, year = {2026}, } Publisher's Version Article: stoc26main-p673-p doi:10.1145/3798129.3800849

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
Elena Grigorescu, Vinayak M. Kumar, Peter Manohar, and Geoffrey Mon
(University of Waterloo, Canada; University of Texas at Austin, USA; Institute for Advanced Study at Princeton, USA)
A locally decodable code (LDC) C ∶ {0,1}^k → {0,1}ⁿ is an error-correcting code that allows one to recover any bit of the original message with good probability while only reading a small number of bits from a corrupted codeword. A relaxed locally decodable code (RLDC) is a weaker notion where the decoder is additionally allowed to abort and output a special symbol ⊥ if it detects an error. For a large constant number of queries q, there is a large gap between the blocklength n of the best-known q-query LDC and the best-known q-query RLDC. Existing constructions of RLDCs achieve polynomial length n = k^{1 + O(1/q)}, while the best-known q-LDCs only achieve subexponential length n = 2^ko(1). On the other hand, for q = 2, RLDCs and LDCs are equivalent as shown by Block, Blocki, Cheng, Grigorescu, Li, Zheng, and Zhu (CCC 2023). We thus ask the question: what is the smallest q such that there exists a q-RLDC that is not a q-LDC?
In this work, we show that any linear 3-query RLDC is in fact a 3-LDC, i.e., linear RLDCs and LDCs are equivalent at 3 queries. More generally, we show for any constant q, there is a soundness error threshold s(q) such that any linear q-RLDC with soundness error below this threshold must be a q-LDC. This implies that linear RLDCs cannot have “strong soundness” — a stricter condition satisfied by linear LDCs that says the soundness error is proportional to the fraction of errors in the corrupted codeword — unless they are simply LDCs.
In addition, we give simple constructions of linear 15-query RLDCs that are not q-LDCs for any constant q, showing that for q = 15, linear RLDCs and LDCs are not equivalent.
We also prove nearly identical results for locally correctable codes and their corresponding relaxed counterpart.

@InProceedings{STOC26p1409, author = {Elena Grigorescu and Vinayak M. Kumar and Peter Manohar and Geoffrey Mon}, title = {Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1409-1416}, doi = {10.1145/3798129.3800850}, year = {2026}, } Publisher's Version Article: stoc26main-p674-p doi:10.1145/3798129.3800850

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
Monika Henzinger, Robin Münk, and Harald Räcke
(IST Austria, Austria; TU Munich, Germany)
A single-commodity congestion approximator for a graph is a compact data structure that approximately predicts the edge congestion required to route any set of single-commodity flow demands in a network. A hierarchical congestion approximator (HCA) consists of a laminar family of cuts in the graph and has numerous applications in approximating cut and flow problems in graphs, designing efficient routing schemes, and managing distributed networks.
There is a tradeoff between the running time for computing an HCA and its approximation quality. The best polynomial-time construction in an n-node graph gives an HCA with approximation quality O(log^1.5n loglogn). Among near-linear time algorithms, the best previous result achieves approximation quality O(log⁴ n). We improve upon the latter result by giving the first near-linear time algorithm for computing an HCA with approximation quality O(log² n loglogn). Additionally, our algorithm can be implemented in the parallel setting with polylogarithmic span and near-linear work, achieving the same approximation quality. This improves upon the best previous such algorithm, which has an O(log⁹n) approximation quality. We also present a lower bound of Ω(logn) for the approximation guarantee of hierarchical congestion approximators.
Crucial for achieving a near-linear running time is a new partitioning routine that, unlike previous such routines, manages to avoid recursing on large subgraphs. To achieve the improved approximation quality, we introduce the new concept of border routability of a cut and provide an improved sparsest cut oracle for general vertex weights.

@InProceedings{STOC26p1417, author = {Monika Henzinger and Robin Münk and Harald Räcke}, title = {An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1417-1428}, doi = {10.1145/3798129.3800851}, year = {2026}, } Publisher's Version Article: stoc26main-p678-p doi:10.1145/3798129.3800851

Near-Optimal Directed Euclidean Spanners in High Dimensions
Rajesh Jayaram, Shyamal Patel, Clifford Stein, Erik Waingarten, and Tian Zhang
(Google Research, USA; Columbia University, USA; University of Pennsylvania, USA)
For any є ∈ (0,1), we give a randomized algorithm which given n points in (^d, ℓ_p) for p ∈ [1,2], constructs a directed graph using O(n^{2 − Ω(є)}) edges in nearly-matching time, such that shortest path lengths approximate ℓ_p-distances up to a (1 + є)-factor. The graph uses non-metric Steiner nodes (known to be necessary) and improves upon the prior construction of Andoni and Zhang using O(n^2−Ω(є2)) edges. We show that our construction is nearly-optimal by showing there exists a set of points in ^d where any (1+є)-approximate directed Steiner spanner must use Ω(n^{2 − O(є)}) edges.
As further applications, we show that our directed Steiner spanner gives faster algorithms for Wasserstein-q distances over (^d,ℓ_p).

@InProceedings{STOC26p1429, author = {Rajesh Jayaram and Shyamal Patel and Clifford Stein and Erik Waingarten and Tian Zhang}, title = {Near-Optimal Directed Euclidean Spanners in High Dimensions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1429-1440}, doi = {10.1145/3798129.3800852}, year = {2026}, } Publisher's Version Article: stoc26main-p703-p doi:10.1145/3798129.3800852

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick
(University of California at Berkeley, USA; University of Michigan, USA; University of Chicago, USA; Tel Aviv University, Israel)
The input to the Multiway Cut problem is a weighted undirected graph, with nonnegative edge weights, and k designated terminals. The goal is to partition the vertices of the graph into k parts, each containing exactly one of the terminals, such that the sum of weights of the edges connecting vertices in different parts of the partition is minimized. The problem is APX-hard for k≥3. The currently best known approximation algorithm for the problem for arbitrary k, obtained by Sharma and Vondrák [STOC 2014] more than a decade ago, has an approximation ratio of 1.2965. We present an algorithm with an improved approximation ratio of 1.2787. Also, for small values of k ≥ 4 we obtain the first improvements in 25 years over the currently best approximation ratios obtained by Karger, Klein, Stein, Thorup, and Young [STOC 1999]. (For k=3 an optimal approximation algorithm is known.)
Our main technical contributions are new insights on rounding the LP relaxation of Călinescu, Karloff, and Rabani [STOC 1998], whose integrality ratio matches Multiway Cut’s approximability ratio, assuming the Unique Games Conjecture [Manokaran, Naor, Raghavendra, and Schwartz, STOC 2008]. First, we introduce a generalized form of a rounding scheme suggested by Kleinberg and Tardos [FOCS 1999] and use it to replace the Exponential Clocks rounding scheme used by Buchbinder, Naor, and Schwartz [STOC 2013] and by Sharma and Vondrák. Second, while previous algorithms use a mixture of two, three, or four basic rounding schemes, each from a different family of rounding schemes, our algorithm uses a computationally-discovered mixture of hundreds of basic rounding schemes, each parametrized by a random variable with a distinct probability distribution, including in particular many different rounding schemes from the same family. We give a completely rigorous analysis of our improved algorithms using a combination of analytical techniques and interval arithmetic.

@InProceedings{STOC26p1441, author = {Joshua Brakensiek and Neng Huang and Aaron Potechin and Uri Zwick}, title = {Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1441-1452}, doi = {10.1145/3798129.3800853}, year = {2026}, } Publisher's Version Article: stoc26main-p713-p doi:10.1145/3798129.3800853

Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
Bartłomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, and Mirza Redžić
(University of Wrocław, Poland; MPI-INF, Germany; KIT, Germany; University of California at Berkeley, USA; Stanford University, USA)
We revisit the complexity of verifying basic identities, such as associativity and distributivity, on a given finite algebraic structure. In particular, while Rajagopalan and Schulman (FOCS'96, SICOMP'00) gave a surprising randomized algorithm to verify associativity of an operation odot: S x S -> S in optimal time O(|S|^2), they left open the problem of finding any subcubic algorithm for verifying distributivity of given operations odot, oplus: S x S -> S.
We resolve the open problem by Rajagopalan and Schulman by devising an algorithm verifying distributivity in strongly subcubic time O(|S|^omega), together with a matching conditional lower bound based on the Triangle Detection Hypothesis. We propose arithmetic progression detection in small universes as a consequential algorithmic challenge: We show that unless 4-term arithmetic progressions in a set X subseteq {1,...,N} can be detected in time O(N^{2-epsilon}), then the 3-uniform 4-hyperclique hypothesis is true, and verifying certain identities requires running time |S|^{3-o(1)}. A careful combination of our algorithmic and hardness ideas allows us to fully classify a natural subclass of identities: Specifically, any 3-variable identity over binary operations in which no side is a subexpression of the other is either verifiable in randomized time O(|S|^2), verifiable in randomized time O(|S|^omega) with a matching lower bound from triangle detection, or trivially verifiable in time O(|S|^3) with a matching lower bound from hardness of 4-term arithmetic progression detection. Finally, we obtain near-optimal algorithms for verifying whether a given algebraic structure forms a field or ring, and show that counting the number of distributive triples is conditionally harder than verifying distributivity.

@InProceedings{STOC26p1453, author = {Bartłomiej Dudek and Nick Fischer and Geri Gokaj and Ce Jin and Marvin Künnemann and Xiao Mao and Mirza Redžić}, title = {Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1453-1464}, doi = {10.1145/3798129.3800854}, year = {2026}, } Publisher's Version Article: stoc26main-p715-p doi:10.1145/3798129.3800854

Locally Computable High Independence Hashing
Yevgeniy Dodis, Shachar Lovett, and Daniel Wichs
(New York University, USA; University of California at San Diego, USA; Northeastern University, USA; NTT Research, USA)
We consider (almost) k-wise independent hash functions, whose evaluations on any k inputs are (almost) uniformly random, for very large values of k. Such hash functions need to have a large key that grows linearly with k. However, it may be possible to evaluate them in sub-linear time by only reading a small subset of t ≪ k locations during each evaluation; we call such hash functions t-local. Such hash functions have applications to nearly optimal bounded-use information-theoretic cryptography. Local hash functions were previously studied in several works starting with Siegel (FOCS’89, SICOMP’04). For a hash function with n-bit input and output size, we get the following new results:
(A) There exist (non-constructively) perfectly k-wise independent t-local hash functions with key size O(kn) and locality of t = O(n) bits. Furthermore, we show that such hash functions could be made explicit if we had explicit optimal constructions of unbalanced bipartite lossless expanders. Plugging in currently best known suboptimal explicit expanders yields correspondingly suboptimal hash functions.
(B) Perfectly k-wise independent local hash functions generically yield expanders with corresponding parameters. This is true even if the locations accessed by the hash function can be chosen adaptively.
(C) We initiate the study of -almost k-wise independent hash functions, where any k adaptive queries to the hash function are є-statistically indistinguishable from k queries to a random function. We construct an explicit family of such hash functions with optimal key size O(kn) bits, optimal locality t = O(n) bits, and = 2⁻ⁿ.
(D) More generally, in a word model with word size w, we get an explicit, efficient construction of -almost k-wise independent hash functions with key size O(kn/w) words, locality t = O(n/√w) words, and statistical distance = 2⁻ⁿ, which we show to be nearly optimal.

@InProceedings{STOC26p1465, author = {Yevgeniy Dodis and Shachar Lovett and Daniel Wichs}, title = {Locally Computable High Independence Hashing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1465-1476}, doi = {10.1145/3798129.3800855}, year = {2026}, } Publisher's Version Article: stoc26main-p718-p doi:10.1145/3798129.3800855

Approximate Orthogonal Vectors and Diameter via Regularity Lemma
Alexandr Andoni, Shunhua Jiang, and Stepan Zharkov
(Columbia University, USA; ETH Zurich, Switzerland)
We develop algorithms for the approximate Orthogonal Vectors (OV) and Diameter problems over the Hamming space. Prior work exhibited an intriguing sharp transition: for approximation factor c=2, the algorithms are simple and run in Õ(nd) time; whereas already for c=2−δ, the best known approach has been to reduce the problems to nearest neighbor search, leading to solutions with runtimes of the form n^1+Ω(1).
Our algorithms solve (2−δ)-approximate OV and Diameter with runtimes of n^1+O(δ) and n^1+O(√δ), respectively. The improvement also holds for the online (data structure) versions: online OV and Furthest Neighbor Search (FNS). This is the first direct improvement for approximate FNS in the Hamming space since [Goel, Indyk, Varadarajan 2001].
Our approach consists of two key steps. First, we define a “heterogeneous” pseudo-random instance of the problems and prove a structural lemma showing that any such instance is solved by one of three simple algorithms. Second, we develop a specialized regularity lemma that allows one to reduce any arbitrary dataset to such a pseudo-random instance.

@InProceedings{STOC26p1477, author = {Alexandr Andoni and Shunhua Jiang and Stepan Zharkov}, title = {Approximate Orthogonal Vectors and Diameter via Regularity Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1477-1488}, doi = {10.1145/3798129.3800856}, year = {2026}, } Publisher's Version Article: stoc26main-p734-p doi:10.1145/3798129.3800856

3-Query RLDCs Are Strictly Stronger Than 3-Query LDCs
Tom Gur, Dor Minzer, Guy Weissenberg, and Kai Zhe Zheng
(University of Cambridge, UK; Massachusetts Institute of Technology, USA; EPFL, Switzerland)
We construct 3-query relaxed locally decodable codes (RLDCs) with constant alphabet size and length Õ(k²) for k-bit messages. Combined with the lower bound of Ω(k³) of [Alrabiah, Guruswami, Kothari, Manohar, STOC 2023] on the length of locally decodable codes (LDCs) with the same parameters, we obtain a separation between RLDCs and LDCs, resolving an open problem of [Ben-Sasson, Goldreich, Harsha, Sudan and Vadhan, SICOMP 2006].
Our RLDC construction relies on two components. First, we give a new construction of probabilistically checkable proofs of proximity (PCPPs) with 3 queries, quasi-linear size, constant alphabet size, perfect completeness, and small soundness error. This improves upon all previous PCPP constructions, which either had a much higher query complexity or soundness close to 1. Second, we give a query-preserving transformation from PCPPs to RLDCs.
At the heart of our PCPP construction is a 2-query decodable PCP (dPCP) with matching parameters, and our construction builds on the HDX-based PCP of [Bafna, Minzer, Vyas, Yun, STOC 2025] and on the efficient composition framework of [Moshkovitz, Raz, JACM 2010] and [Dinur, Harsha, SICOMP 2013]. More specifically, we first show how to use the HDX-based construction to get a dPCP with matching parameters but a large alphabet size, and then prove an appropriate composition theorem (and related transformations) to reduce the alphabet size in dPCPs.

@InProceedings{STOC26p1489, author = {Tom Gur and Dor Minzer and Guy Weissenberg and Kai Zhe Zheng}, title = {3-Query RLDCs Are Strictly Stronger Than 3-Query LDCs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1489-1496}, doi = {10.1145/3798129.3800857}, year = {2026}, } Publisher's Version Info Article: stoc26main-p741-p doi:10.1145/3798129.3800857

Pattern-Sparse Tree Decompositions in H-Minor-Free Graphs
Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk
(CISPA Helmholtz Center for Information Security, Germany; University of Warsaw, Poland)
Given an H-minor-free graph G and an integer k, our main technical contribution is sampling in randomized polynomial time an induced subgraph G′ of G and a tree decomposition of G′ of width O(k) such that for every Z⊆ V(G) of size k, with probability at least (2^O(√k)|V(G)|^O(1))⁻¹, we have Z ⊆ V(G′) and every bag of the tree decomposition contains at most O(√k) vertices of Z. Having such a tree decomposition allows us to solve a wide range of problems in (randomized) time 2^O(√k)n^O(1) where the solution is a pattern Z of size k, e.g., Directed k-Path, H-Packing, etc. In particular, our result recovers all the algorithmic applications of the pattern-covering result of Fomin et al. [SIAM J. Computing 2022] (which requires the pattern to be connected) and the planar subgraph-finding algorithms of Nederlof [STOC 2020].
Furthermore, for K_h,3-free graphs (which include bounded-genus graphs) and for a fixed constant d, we signficantly strengthen the result by ensuring that not only Z has intersection O(√k) with each bag, but even the distance-d neighborhood N_G^d[Z] as well. This extension makes it possible to handle a wider range of problems where the neighborhood of the pattern also plays a role in the solution, such as partial domination problems and problems involving distance constraints.

@InProceedings{STOC26p1497, author = {Dániel Marx and Marcin Pilipczuk and Michał Pilipczuk}, title = {Pattern-Sparse Tree Decompositions in H-Minor-Free Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1497-1507}, doi = {10.1145/3798129.3800858}, year = {2026}, } Publisher's Version Article: stoc26main-p775-p doi:10.1145/3798129.3800858

A Dobrushin Condition for Quantum Markov Chains: Rapid Mixing and Conditional Mutual Information at High Temperature
Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang
(New York University, USA; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA)
A central challenge in quantum physics is to understand the structural properties of many-body systems, both in equilibrium and out of equilibrium. For classical systems, we have a unified perspective which connects structural properties of systems at thermal equilibrium to the Markov chain dynamics that mix to them. We lack such a perspective for quantum systems: there is no framework to translate the quantitative convergence of the Markovian evolution into strong structural consequences.
We develop a general framework that brings the breadth and flexibility of the classical theory to quantum Gibbs states at high temperature. At its core is a natural quantum analog of a Dobrushin condition; whenever this condition holds, a concise path-coupling argument proves rapid mixing for the corresponding Markovian evolution. The same machinery bridges dynamic and structural properties: rapid mixing yields exponential decay of conditional mutual information (CMI) without restrictions on the size of the probed subsystems, resolving a central question in the theory of open quantum systems. Our key technical insight is an optimal transport viewpoint which couples quantum dynamics to a linear differential equation, enabling precise control over how local deviations from equilibrium propagate to distant sites.

@InProceedings{STOC26p1508, author = {Ainesh Bakshi and Allen Liu and Ankur Moitra and Ewin Tang}, title = {A Dobrushin Condition for Quantum Markov Chains: Rapid Mixing and Conditional Mutual Information at High Temperature}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1508-1516}, doi = {10.1145/3798129.3800859}, year = {2026}, } Publisher's Version Article: stoc26main-p776-p doi:10.1145/3798129.3800859

Improved Bounds for Coin Flipping, Leader Election, and Random Selection
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Rocco A. Servedio
(Cornell University, USA; Columbia University, USA)
Random selection is a fundamental task in fault-tolerant distributed computing where processors select a random outcome from some domain. Two special cases of this, leader election (where the processors designate a leader amongst themselves) and collective coin flipping (where the processors agree on a common random bit), have been especially widely studied. We study these problems in the full-information model, where processors communicate via a single broadcast channel, have access to private randomness, and face a computationally unbounded adversary that controls some of the processors. Despite decades of study, key gaps remain in our understanding of the trade-offs between round complexity, communication per player in each round, and adversarial resilience. We make progress by proving new lower bounds for coin flipping protocols and both new upper and lower bounds for leader election and random selection protocols.
We first show that any k-round coin flipping protocol, where each of ℓ players sends 1 bit per round, can be biased by O(ℓ/log^(k)(ℓ)) bad players. We obtain the same lower bound (with an additional log^(k+1)(ℓ) factor in the numerator) for leader election as well. This strengthens the previous best lower bounds [RSZ, SICOMP 2002], which ruled out coin flipping protocols resilient to O(ℓ / log^(2k−1)(ℓ)) bad players and leader election protocols resilient to O(ℓ / log^(2k+1)(ℓ)) bad players. As a consequence, we establish that any protocol tolerating a linear fraction of corrupt players, while restricting player messages to 1 bit per round, must run for at least log^* ℓ − O(1) rounds, improving on the prior best lower bound of 1/2 log^* ℓ − log^* log^* ℓ. We additionally show that the current best protocols that handle a linear number of corrupt players (from [RZ, JCSS 2001], [F, FOCS 1999]) are near optimal in terms of round complexity and communication per player in a round.
We next initiate the study of one-round random selection protocols where each player sends 1 bit in the round. For all m ≥ (log(ℓ))², we obtain an optimal one-round protocol: We construct a protocol that is resilient to O(ℓ / m) bad players, outputting m uniform random bits. And, we show that any protocol that outputs m uniform random bits can be corrupted using O(ℓ / m) bad players. As far as we are aware, this is the first provably optimal protocol for any task in the full information model.
As a consequence of our construction, we obtain a one-round leader election protocol resilient to ℓ / (log(ℓ))² bad players, improving on the previous best protocol from [RZ, JCSS 2001] that is resilient to only ℓ / (log(ℓ))³ bad players and requires players to send many bits. When m = (log(ℓ))², our resilience parameter matches that of the best one-round coin flipping protocol by Ajtai and Linial, which only outputs one bit. To obtain our lower bound, we introduce and study multi-output influence, a natural extension of the notion of influence of boolean functions to the multi-output setting.

@InProceedings{STOC26p1517, author = {Eshan Chattopadhyay and Mohit Gurumukhani and Noam Ringach and Rocco A. Servedio}, title = {Improved Bounds for Coin Flipping, Leader Election, and Random Selection}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1517-1527}, doi = {10.1145/3798129.3800860}, year = {2026}, } Publisher's Version Article: stoc26main-p777-p doi:10.1145/3798129.3800860

Planar Length-Constrained Minimum Spanning Trees
D Ellis Hershkowitz and Richard Z Huang
(Brown University, USA)
In length-constrained minimum spanning tree (MST) we are given an n-node graph G = (V,E) with edge weights w : E → ℤ_{≥ 0} and edge lengths l: E → ℤ_{≥ 0} along with a root node r ∈ V and a length constraint h ∈ ℤ_{≥ 0}. Our goal is to output a spanning tree of minimum weight according to w in which every node is at distance at most h from r according to l.
We give a polynomial-time algorithm for planar graphs which, for any constant є > 0, outputs an O(log^1+є n)-approximate solution with every node at distance at most (1+є)h from r. Our algorithm is based on new length-constrained versions of classic planar separators and divisions which may be of independent interest. Additionally, our algorithm works for length-constrained Steiner tree and bounds the integrality gap of the natural linear program as O(log² n /є), again with (1+є) slack in the length constraint. Complementing this, we show that any algorithm on general graphs for length-constrained MST in which nodes are at most 2h from r cannot achieve an approximation of O(log^2−є n) for any constant є > 0 under standard complexity assumptions; as such, our results separate the approximability of length-constrained MST in planar and general graphs.

@InProceedings{STOC26p1528, author = {D Ellis Hershkowitz and Richard Z Huang}, title = {Planar Length-Constrained Minimum Spanning Trees}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1528-1539}, doi = {10.1145/3798129.3800861}, year = {2026}, } Publisher's Version Article: stoc26main-p778-p doi:10.1145/3798129.3800861

Approximating Directed Connectivity in Almost-Linear Time
Kent Quanrud
(Purdue University, USA)
We present randomized algorithms that compute (1+ε)-approximate minimum global edge and vertex cuts in weighted directed graphs in O(log⁴(n) / ε) and O(log⁵(n) / ε) single-commodity flows, respectively. With recent almost-linear time maximum flow algorithms, this gives almost-linear time approximation schemes for edge and vertex connectivity. By setting ε appropriately, this also gives faster exact algorithms for small vertex connectivity.
At the heart of these algorithms is a divide-and-conquer technique called ”shrink-wrapping” for a certain well-conditioned rooted Steiner connectivity problem. Loosely speaking, for a root r and a set of terminals, shrink-wrapping uses flow to certify the connectivity from a root r to some of the terminals, and for the remaining uncertified terminals, generates an r-cut where the sink component both (a) contains the sink component of the minimum (r,t)-cut for each uncertified terminal t and (b) has size proportional to the number of uncertified terminals. This yields a divide-and-conquer scheme over the terminals where we can divide the set of terminals and compute their respective minimum r-cuts in smaller, contracted subgraphs.

@InProceedings{STOC26p1540, author = {Kent Quanrud}, title = {Approximating Directed Connectivity in Almost-Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1540-1547}, doi = {10.1145/3798129.3800862}, year = {2026}, } Publisher's Version Article: stoc26main-p791-p doi:10.1145/3798129.3800862

An Optimal Algorithm for Stochastic Vertex Cover
Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Clifford Stein, Miltiadis Stouras, Ola Svensson, and Ali Vakilian
(Georgia Institute of Technology, USA; DTU, Denmark; Stanford University, USA; Duke University, USA; Columbia University, USA; EPFL, Switzerland; Virginia Tech, USA)
The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph G^⋆ that is realized by sampling each edge independently with some probability p∈ (0, 1] in a base graph G = (V, E). The algorithm is given the base graph G and the probability p as inputs, but its only access to the realized graph G^⋆ is through queries on individual edges in G that reveal the existence (or not) of the queried edge in G^⋆. In this paper, we resolve the central open question for this problem: to find a (1+ε)-approximate vertex cover using only O_ε(n/p) edge queries. Prior to our work, there were two incomparable state-of-the-art results for this problem: a (3/2+ε)-approximation using O_ε(n/p) queries (Derakhshan, Durvasula, and Haghtalab, 2023) and a (1+ε)-approximation using O_ε((n/p)· RS(n)) queries (Derakhshan, Saneian, and Xun, 2025), where RS(n) is known to be at least 2^{Ω(logn/loglogn)} and could be as large as n/2^{Θ(log* n)}. Our improved upper bound of O_ε(n/p) matches the known lower bound of Ω(n/p) for any constant-factor approximation algorithm for this problem (Behnezhad, Blum, and Derakhshan, 2022). A key tool in our result is a new concentration bound for the size of minimum vertex cover on random graphs, which might be of independent interest.

@InProceedings{STOC26p1548, author = {Jan van den Brand and Inge Li Gørtz and Chirag Pabbaraju and Debmalya Panigrahi and Clifford Stein and Miltiadis Stouras and Ola Svensson and Ali Vakilian}, title = {An Optimal Algorithm for Stochastic Vertex Cover}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1548-1557}, doi = {10.1145/3798129.3800863}, year = {2026}, } Publisher's Version Article: stoc26main-p798-p doi:10.1145/3798129.3800863

Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes
Rohan Goyal and Venkatesan Guruswami
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)
Reed-Solomon (RS) codes were recently shown to exhibit an intriguing proximity gap phenomenon. Specifically, given a collection of strings with some algebraic structure (such as belonging to a line or affine space), either all of them are δ-close to RS codewords, or most of them are δ-far from the code. Here δ is the proximity parameter which can be taken to be the Johnson radius 1−√R of the RS code (R being the code rate), matching its best known list-decodability. Proximity gaps play a crucial role in the soundness analysis of Interactive Oracle Proof (IOP) protocols used in Succinct Non-Interactive Arguments of Knowledge (SNARKs) and the resulting proof sizes.
Proving proximity gaps beyond the Johnson radius, and in particular approaching 1−R (which is best possible), has been posed multiple times as a challenge with significant practical consequences to the efficiency of SNARKs. Here we prove that variants of RS codes, such as folded RS codes and univariate multiplicity codes, indeed have proximity gaps for δ approaching 1−R. The result applies more generally to codes with a certain subspace-design property. Our proof hinges on a clean property we abstract called line (or more generally curve) decodability, which we establish leveraging and adapting techniques from recent progress on list-decoding such codes. Importantly, our analysis avoids the heavy algebraic machinery used in previous works, and requires a field size only linear in the block length.
The behavior of subspace-design codes w.r.t “local properties” has recently been shown to be similar to random linear codes and random RS codes (where the evaluation points are chosen at random from the underlying field). We identify a local property that implies curve decodability, and thus also proximity gaps, and thereby conclude that random linear and random RS codes also exhibit proximity gaps up to the 1−R bound. Our results also establish the stronger (mutual) correlated agreement property which implies proximity gaps. Additionally, we also show a slacked proximity gap theorem for constant-sized fields using AEL-based constructions and local property techniques.

@InProceedings{STOC26p1558, author = {Rohan Goyal and Venkatesan Guruswami}, title = {Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1558-1568}, doi = {10.1145/3798129.3800864}, year = {2026}, } Publisher's Version Article: stoc26main-p809-p doi:10.1145/3798129.3800864

Polynomial Identity Testing and the Ideal Proof System: PIT Is in NP If and Only If IPS Can Be p-Simulated by a Cook-Reckhow Proof System
Joshua A. Grochow
(University of Colorado Boulder, USA)
The Ideal Proof System (IPS) of Grochow & Pitassi (FOCS 2014, J. ACM, 2018) is an algebraic proof system that uses algebraic circuits to refute the solvability of unsatisfiable systems of polynomial equations. One potential drawback of IPS is that verifying an IPS proof is only known to be doable using Polynomial Identity Testing (PIT), which is solvable by a randomized algorithm, but whose derandomization, even into NSUBEXP, is equivalent to strong lower bounds. However, the circuits that are used in IPS proofs are not arbitrary, and it is conceivable that one could get around general PIT by leveraging some structure in these circuits. This proposal may be even more tempting when IPS is used as a proof system for Boolean Unsatisfiability, where the equations themselves have additional structure.
Our main result is that, on the contrary, one cannot get around PIT as above: we show that IPS, even as a proof system for Boolean Unsatisfiability, can be p-simulated by a deterministically verifiable (Cook-Reckhow) proof system if and only if PIT is in NP (with some technical caveats about the relationship between the field used for IPS and that used for PIT). We use our main result to propose a potentially new approach to derandomizing PIT into NP.

@InProceedings{STOC26p1569, author = {Joshua A. Grochow}, title = {Polynomial Identity Testing and the Ideal Proof System: PIT Is in NP If and Only If IPS Can Be p-Simulated by a Cook-Reckhow Proof System}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1569-1580}, doi = {10.1145/3798129.3800865}, year = {2026}, } Publisher's Version Article: stoc26main-p813-p doi:10.1145/3798129.3800865

Learning Functions of Halfspaces
Josh Alman, Shyamal Patel, and Rocco A. Servedio
(Columbia University, USA)
We give an algorithm that learns arbitrary Boolean functions of k arbitrary halfspaces over Rⁿ, in the challenging distribution-free Probably Approximately Correct (PAC) learning model, running in time 2^{√n · (logn)O(k)}. This is the first algorithm that can PAC learn even intersections of two halfspaces in time 2^o(n).

@InProceedings{STOC26p1581, author = {Josh Alman and Shyamal Patel and Rocco A. Servedio}, title = {Learning Functions of Halfspaces}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1581-1591}, doi = {10.1145/3798129.3800866}, year = {2026}, } Publisher's Version Article: stoc26main-p827-p doi:10.1145/3798129.3800866

Failure of Symmetry of Information for Randomized Computations
Jinqiao Hu, Yahel Manor, and Igor C. Oliveira
(University of Warwick, UK; University of Haifa, Israel)
Symmetry of Information (SoI) is a fundamental result in Kolmogorov complexity stating that for all n-bit strings x and y, we have K(x,y) = K(y) + K(x ∣ y) up to an additive error of O(logn). In contrast, understanding whether SoI holds for time-bounded Kolmogorov complexity measures is closely related to longstanding open problems in complexity theory and cryptography, such as the P versus NP question and the existence of one-way functions.
In this paper, we prove that SoI fails for rKt complexity, the randomized analogue of Levin’s Kt complexity. This is the first unconditional result of this type for a randomized notion of time-bounded Kolmogorov complexity. More generally, we establish a close relationship between the validity of SoI for rKt and the existence of randomized algorithms approximating rKt(x). Motivated by applications in cryptography, we also establish the failure of SoI for a related notion called pKt complexity, and provide an extension of the results to the average-case setting. Finally, we prove a near-optimal lower bound on the complexity of estimating conditional rKt, a result that might be of independent interest.

@InProceedings{STOC26p1592, author = {Jinqiao Hu and Yahel Manor and Igor C. Oliveira}, title = {Failure of Symmetry of Information for Randomized Computations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1592-1603}, doi = {10.1145/3798129.3800867}, year = {2026}, } Publisher's Version Article: stoc26main-p834-p doi:10.1145/3798129.3800867

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
Julia Chuzhoy, Sanjeev Khanna, and Junkai Song
(Toyota Technological Institute at Chicago, USA; New York University, USA)
In the fully dynamic maximal matching problem, the goal is to maintain a maximal matching in a graph undergoing an online sequence of edge insertions and deletions, while minimizing the update time. The problem has been studied extensively in the oblivious-adversary setting, where randomized algorithms with polylogarithmic worst-case and constant amortized update time have been known for some time. A major challenge in this area has been designing an algorithm with non-trivial update time against an adaptive adversary, who may explicitly tailor the update sequence to the algorithm’s choices. In a recent breakthrough, Bernstein, Bhattacharya, Kiss, and Saranurak (STOC 2025; hereafter, BBKS25) obtained the first algorithms with sublinear in n update time for this setting: namely, a randomized algorithm with Õ(n^3/4) amortized update time, and a deterministic algorithm with Õ(n^8/9) amortized update time. Our main result is a deterministic algorithm for fully dynamic maximal matching with amortized update time n^1/2+o(1).
A powerful tool in dynamic matching is the use of matching sparsifiers: sparse subgraphs that preserve enough information to recover matchings with desired properties. Sparsifiers have been successfully used for approximate maximum matching, yielding sublinear update-time algorithms even against adaptive adversaries. For maximal matching, however, this paradigm is not as natural, since maximality must hold with respect to the entire graph, and so the algorithm must be able to detect and repair violations across all edges. Nevertheless, BBKS25 showed that the EDCS data structure can be ingeniously repurposed as a verification-and-repair mechanism for fully dynamic maximal matching against adaptive adversaries.
We introduce a new deterministic framework, referred to as the subgraph system, which, in contrast to the EDCS data structure used by BBKS25, is purpose-built for verification and maintenance of maximality. The structure of the subgraph system is also carefully designed to allow efficient recursive refinements leading to stronger and stronger parameters. This recursive approach yields our deterministic algorithm with n^1/2+o(1) amortized update time, and provides a new deterministic framework for one of the central graph optimization problems in the dynamic setting.

@InProceedings{STOC26p1604, author = {Julia Chuzhoy and Sanjeev Khanna and Junkai Song}, title = {A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1604-1615}, doi = {10.1145/3798129.3800868}, year = {2026}, } Publisher's Version Article: stoc26main-p840-p doi:10.1145/3798129.3800868

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
Sitan Chen, Jingqiu Ding, Mahbod Majid, and Walter McKelvie
(Harvard University, USA; ETH Zurich, Switzerland; Massachusetts Institute of Technology, USA)
Bayesian methods lie at the heart of modern data science and provide a powerful scaffolding for estimation in data-constrained settings and principled quantification and propagation of uncertainty. Yet in many real-world use cases where these methods are deployed, there is a natural need to preserve the privacy of the individuals whose data is being scrutinized. While a number of works have attempted to approach the problem of differentially private Bayesian estimation through either reasoning about the inherent privacy of the posterior distribution or privatizing off-the-shelf Bayesian methods, these works generally do not come with rigorous utility guarantees beyond low-dimensional settings. In fact, even for the prototypical tasks of Gaussian mean estimation and linear regression, it was unknown how close one could get to the Bayes-optimal error with a private algorithm, even in the simplest case where the unknown parameter comes from a Gaussian prior.
In this work, we give the first polynomial-time algorithms for both of these problems that achieve mean-squared error (1 + o(1))OPT and additionally show that both tasks exhibit an intriguing computational-statistical gap. For Bayesian mean estimation, we prove that the excess risk achieved by our method is optimal among all efficient algorithms within the low-degree framework, yet is provably worse than what is achievable by an exponential-time algorithm. For linear regression, we prove a qualitatively similar such lower bound. Our algorithms draw upon the privacy-to-robustness framework, but with the curious twist that to achieve private Bayes-optimal estimation, we need to design sum-of-squares-based robust estimators for inherently non-robust objects like the empirical mean and OLS estimator. Along the way we also add to the sum-of-squares toolkit a new kind of constraint based on short-flat decompositions.

@InProceedings{STOC26p1616, author = {Sitan Chen and Jingqiu Ding and Mahbod Majid and Walter McKelvie}, title = {Computation-Utility-Privacy Tradeoffs in Bayesian Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1616-1626}, doi = {10.1145/3798129.3800869}, year = {2026}, } Publisher's Version Article: stoc26main-p850-p doi:10.1145/3798129.3800869

Sub-linear Secure Broadcast and Applications
Yuval Gelles, Ilan Komargodski, and Merav Parter
(Hebrew University of Jerusalem, Israel; Weizmann Institute of Science, Israel)
We present improved distributed broadcast and MST algorithms that are unconditionally secure against an eavesdropper controlling a fixed set of at most f edges in an n-node m-edge D-diameter graph. We strive for secure algorithms with sublinear round and subquadratic message complexities (in n) for any f. This is in contrast to the exponential or polynomial dependence on f in prior works. Our main results are:
Secure broadcast algorithm, for sending an O(logn)-bit message, that runs in Õ(D+√n) rounds and Õ(n^3/2) messages. This matches the state-of-the-art bounds for insecure broadcast by [Ghaffari and Kuhn, and Gmyr and Pandurangan, DISC 2018]. Our bounds also improve over the Õ(D+√f n)-round complexity and Õ(√f n· m) message complexity of secure broadcast by [Hitron, Parter and Yogev, DISC 2022].
Secure MST algorithm with sublinear round and subcubic message complexities that improve over the algorithm by [Hitron, Parter and Yogev, ITCS 2023] in the entire regime. In particular, when f=Θ(n), we improve the round complexity from Õ(n^3/2) to Õ(n^2/3), and the message complexity from Õ(n³) to Õ(n^7/3).
Our algorithms are randomized and their correctness and (statistical) security hold with high probability. The algorithms are based on a combination of techniques: Karger’s sampling, tree packing and sparse recovery sketches.

@InProceedings{STOC26p1627, author = {Yuval Gelles and Ilan Komargodski and Merav Parter}, title = {Sub-linear Secure Broadcast and Applications}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1627-1638}, doi = {10.1145/3798129.3800870}, year = {2026}, } Publisher's Version Article: stoc26main-p851-p doi:10.1145/3798129.3800870

Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng
(Yale University, USA; Massachusetts Institute of Technology, USA; University of Southern California, USA; University of Virginia, USA)
Learning and computation of equilibria are central problems in game theory, theory of computation, and artificial intelligence. In this work, we introduce proximal regret, a new notion of regret based on proximal operators that lies strictly between external and swap regret. When every player employs a no-proximal-regret algorithm in a general convex game, the empirical distribution of play converges to proximal correlated equilibria (PCE), a refinement of coarse correlated equilibria. Our framework unifies several emerging notions in online learning and game theory—such as gradient equilibrium and semicoarse correlated equilibrium—and introduces new ones. Our main result shows that the classic Online Gradient Descent (GD) algorithm achieves an optimal O(√T) bound on proximal regret, revealing that GD, without modification, minimizes a stronger regret notion than external regret. This provides a new explanation for the empirically superior performance of gradient descent in online learning and games. We further extend our analysis to Mirror Descent in the Bregman setting and to Optimistic Gradient Descent, which yields faster convergence in smooth convex games.

@InProceedings{STOC26p1639, author = {Yang Cai and Constantinos Daskalakis and Haipeng Luo and Chen-Yu Wei and Weiqiang Zheng}, title = {Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1639-1650}, doi = {10.1145/3798129.3800871}, year = {2026}, } Publisher's Version Article: stoc26main-p859-p doi:10.1145/3798129.3800871

Settling the Pass Complexity of Streaming Set Cover
Sepehr Assadi and Janani Sundaresan
(University of Waterloo, Canada)
In the streaming set cover problem, m sets from a universe of size n are arriving one by one in a stream, and the algorithm is allowed to process the stream using one or a few passes and a space of o(mn), which is sublinear in the input size. The goal is to determine the minimal (or approximately minimal) number of sets that cover the universe at the end of the last pass.
This problem has been studied extensively over the years with rapid progress that led to several O(logn)-approximation algorithms in Õ(mn^1/p) space and p passes. However, progress on this front has largely stagnated over the past decade, despite the absence of any lower bounds that rule out even an O(logn)-approximation in O(m) space and just two passes.
We provide a simple explanation for this lack of progress by establishing an optimal three-way space-pass-approximation tradeoff for this problem: any α-approximation algorithm for streaming set cover requires Ω(m/α · (n/α)^1/p) space in p passes whenever α ≪ n^1/(p+1).
In light of prior work, this result is optimal (up to logarithmic factors) for any p and α≥ p. Our bound is optimal with respect to the range of α also, and fully settles the complexity of this fundamental problem in the streaming model. The proof of this result is (surprisingly) simple and non-technical and relies on a randomized reduction from a variant of the standard pointer chasing problem in communication complexity, using elementary properties of random sets.

@InProceedings{STOC26p1651, author = {Sepehr Assadi and Janani Sundaresan}, title = {Settling the Pass Complexity of Streaming Set Cover}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1651-1659}, doi = {10.1145/3798129.3800872}, year = {2026}, } Publisher's Version Article: stoc26main-p871-p doi:10.1145/3798129.3800872

Non-adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-Like Inequality for Permutations
Itai Dinur, Nathan Keller, and Avichai Marmor
(Ben-Gurion University of the Negev, Israel; Georgetown University, USA; Bar-Ilan University, Israel)
The power of adaptivity in algorithms has been intensively studied in diverse areas of theoretical computer science. In this paper, we obtain a number of sharp lower bound results which show that adaptivity provides a significant extra power in cryptanalytic time-space tradeoffs with (possibly unlimited) preprocessing time.
Most notably, we consider the discrete logarithm (DLOG) problem in a generic group of N elements. The classical ‘baby-step giant-step’ algorithm for the problem has time complexity T=O(√N), uses O(√N) bits of space (up to logarithmic factors in N) and achieves constant success probability.
We examine a generalized setting where an algorithm obtains an advice string of S bits and is allowed to make T arbitrary non-adaptive queries that depend on the advice string (but not on the challenge group element for which the DLOG needs to be computed).
We show that in this setting, the T=O(√N) online time complexity of the baby-step giant-step algorithm cannot be improved, unless the advice string is more than Ω(√N) bits long. This lies in stark contrast with the classical adaptive Pollard’s rho algorithm for DLOG, which can exploit preprocessing to obtain the tradeoff curve ST²=O(N). We obtain similar sharp lower bounds for the problem of breaking the Even-Mansour cryptosystem in symmetric-key cryptography and for several other problems.
To obtain our results, we present a new model that allows analyzing non-adaptive preprocessing algorithms for a wide array of search and decision problems in a unified way.
Since previous proof techniques inherently cannot distinguish between adaptive and non-adaptive algorithms for the problems in our model, they cannot be used to obtain our results. Consequently, we rely on information-theoretic tools for handling distributions and functions over the space S_N of permutations of N elements. Specifically, we use a variant of Shearer’s lemma for this setting, due to Barthe, Cordero-Erausquin, Ledoux, and Maurey (2011), and a variant of the concentration inequality of Gavinsky, Lovett, Saks and Srinivasan (2015) for read-k families of functions, that we derive from it. This seems to be the first time a variant of Shearer’s lemma for permutations is used in an algorithmic context, and it is expected to be useful in other lower bound arguments.

@InProceedings{STOC26p1660, author = {Itai Dinur and Nathan Keller and Avichai Marmor}, title = {Non-adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-Like Inequality for Permutations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1660-1671}, doi = {10.1145/3798129.3800873}, year = {2026}, } Publisher's Version Article: stoc26main-p879-p doi:10.1145/3798129.3800873

Learning Read-Once Determinants and the Principal Minor Assignment Problem
Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Chandan Saha
(IISc Bangalore, India; IIT Kharagpur, India; ISI Kolkata, India; IIT Bombay, India; Ohio State University, USA)
A symbolic determinant under rank-one restriction computes a polynomial of the form det(A₀ + A₁y₁ + … + A_ny_n), where A₀, A₁, …, A_n are square matrices over a field F and rank(A_i) = 1 for each i ∈ [n]. This class of polynomials has been studied extensively, since the work of Edmonds (1967), in the context of linear matroids, matching, matrix completion and polynomial identity testing. We study the following learning problem for this class: Given black-box access to an n-variate polynomial f = det(A₀ + A₁y₁ + … + A_ny_n), where A₀, A₁, …, A_n are unknown square matrices over F and rank(A_i) = 1 for each i ∈ [n], find a square matrix B₀ and rank-one square matrices B₁, …, B_n over F such that f = det(B₀ + B₁y₁ + … + B_ny_n). In this work, we give a randomized poly(n) time algorithm to solve this problem; the algorithm can be derandomized in quasi-polynomial time. To our knowledge, this is the first efficient learning algorithm for this class. As the above-mentioned class is known to be equivalent to the class of read-once determinants (RODs), we will refer to the problem as learning RODs. An ROD computes the determinant of a matrix whose entries are field constants or variables and every variable appears at most once in the matrix. Thus, the class of RODs is a rare example of a well-studied class of polynomials that admits efficient proper learning.
The algorithm for learning RODs is obtained by connecting with a well-known open problem in linear algebra, namely the Principal Minor Assignment Problem (PMAP), which asks to find (if possible) a matrix having prescribed principal minors. PMAP has also been studied in machine learning to learn the kernel matrix of a determinantal point process. Here, we study a natural black-box version of PMAP: Given black-box access to an n-variate polynomial f = det(A + Y), where A ∈ F^{n × n} is unknown and Y = diag(y₁, …, y_n), find a B ∈ F^{n× n} such that f = det(B + Y). We show that black-box PMAP can be solved in randomized poly(n) time, and further, it is randomized polynomial-time equivalent to learning RODs. The algorithm and the reduction between the two problems can be derandomized in quasi-polynomial time. To our knowledge, no efficient algorithm to solve this black-box version of PMAP was known before. The insights developed along the way also help us give the first NC algorithm for the Principal Minor Equivalence problem, which asks to check if two given matrices have equal corresponding principal minors.

@InProceedings{STOC26p1672, author = {Abhiram Aravind and Abhranil Chatterjee and Sumanta Ghosh and Rohit Gurjar and Roshan Raj and Chandan Saha}, title = {Learning Read-Once Determinants and the Principal Minor Assignment Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1672-1683}, doi = {10.1145/3798129.3800875}, year = {2026}, } Publisher's Version Article: stoc26main-p909-p doi:10.1145/3798129.3800875

Language Generation and Identification from Partial Enumeration: Tight Density Bounds and Topological Characterizations
Jon Kleinberg and Fan Wei
(Cornell University, USA; Duke University, USA)
The recent successes of large language models (LLMs) have led to active lines of work in formal theories of language generation and learning. We build on one such theory, language generation in the limit, in which an adversary enumerates the strings of an unknown language K drawn from a countable list of candidate languages, and an algorithm tries to generate unseen strings from the language. Initial work on this model showed there is an algorithm that can always succeed at this task, and more recent work has shown there is in fact an algorithm that can produce a positive-density subset of the language. These results on density reflect the validity–breadth tension in language generation: the trade-off between generating only valid strings while also achieving wide coverage of the true language.
Here we begin by resolving one of the main open questions from this work on density, establishing a tight bound of 1/2 on the best achievable lower density of any algorithm. We then consider a more powerful adversary, capturing the fact that generation algorithms may typically be faced with an environment in which only a subset of the language is being produced. This is a model with only partial enumeration of K: We show that there is an algorithm with the property that if an adversary only outputs an infinite subset C of the true language K, it can still achieve language generation in the limit; and moreover, if the subset C has lower density α in K, then the algorithm produces a subset of lower density at least α/2, which matches the upper bound. This generalizes the tight density bound of 1/2 to the case where the algorithm must come within 1/2 of the density of whichever subset of K the adversary reveals.
We also revisit the classical Gold-Angluin model of language identification (rather than generation) when the adversary need only partially enumerate an infinite subset C of the true language K. We characterize when it is possible for an algorithm to achieve the natural analogue of identification in the limit in this partial setting, producing languages M_t (and finite representations of them) such that eventually C ⊆ M ⊆ K. Our characterization builds on our earlier topological approach on density in language generation [], and in the process we give a new topological formulation of Angluin’s characterization for language identification in the limit, showing that her condition is precisely equivalent to some appropriate topological space having the T_D separation property.

@InProceedings{STOC26p1684, author = {Jon Kleinberg and Fan Wei}, title = {Language Generation and Identification from Partial Enumeration: Tight Density Bounds and Topological Characterizations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1684-1691}, doi = {10.1145/3798129.3800876}, year = {2026}, } Publisher's Version Article: stoc26main-p926-p doi:10.1145/3798129.3800876

Approximation Algorithms for Satisfiable and Nearly Satisfiable Ordering CSPs
Yury Makarychev
(Toyota Technological Institute at Chicago, USA)
We study approximation algorithms for satisfiable and nearly satisfiable instances of ordering constraint satisfaction problems (ordering CSPs). Ordering CSPs arise naturally in ranking and scheduling, yet their approximability remains poorly understood beyond a few isolated cases. Apart from tractable cases in which satisfiable instances can be solved exactly in polynomial time, prior nontrivial guarantees in the satisfiable regime were known only for Betweenness, while prior algorithms in the nearly satisfiable regime applied only to bounded-arity precedence CSPs – CSPs whose constraints are conjunctions of clauses of the form x_i < x_j.
We introduce a general framework for designing approximation algorithms for ordering CSPs. The framework relaxes an input instance to an auxiliary ordering CSP, solves the relaxation, and then applies a randomized transformation to obtain an ordering for the original instance. This reduces the search for approximation algorithms to an optimization problem over randomized transformations.
Our main technical contribution is to show that the power of this framework is captured by a structured class of transformations, which we call strong IDU transformations: every transformation used in the framework can be replaced by a strong IDU transformation without weakening the resulting approximation guarantee. We then classify strong IDU transformations and show that optimizing over them reduces to an explicit optimization problem whose dimension depends only on the maximum predicate arity k and the desired precision δ > 0. As a consequence, for any finite ordering constraint language, we can compute a strong IDU transformation whose guarantee is within δ of the best guarantee achievable by the framework, in time depending only on k and δ.
The framework applies broadly and yields nontrivial approximation guarantees for a wide class of ordering predicates; the following arity-4 results illustrate its scope. Among NP-hard ordering CSPs defined by a single predicate of arity 4, we show that at least 15051 CSPs admit nontrivial approximation in the satisfiable regime. Moreover, among NP-hard and polynomial-time solvable single-predicate ordering CSPs of arity 4 – excluding bounded-arity precedence CSPs – at least 843 predicates admit nontrivial approximation in the nearly satisfiable regime. Specifically, given a (1−ε)-satisfiable instance, our algorithm produces an ordering that satisfies at least an α − O(ε logn loglogn) fraction of the constraints, where α > α_random depends only on the predicate.

@InProceedings{STOC26p1692, author = {Yury Makarychev}, title = {Approximation Algorithms for Satisfiable and Nearly Satisfiable Ordering CSPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1692-1703}, doi = {10.1145/3798129.3800877}, year = {2026}, } Publisher's Version Article: stoc26main-p928-p doi:10.1145/3798129.3800877

Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-In
Shubhangi Saraf, Devansh Shringi, and Narmada Varadarajan
(University of Toronto, Canada)
In this paper, we give the first subexponential (in fact, quasi-polynomial time) reconstruction algorithm for depth-3 circuits of any constant top fan-in (ΣΠΣ(k) circuits) over ℝ, ℂ, or any large characteristic finite field F. More explicitly, we show that for any constant k, given black-box access to an n-variate polynomial f computed by a ΣΠΣ(k) circuit of size s, there is a randomized algorithm that runs in time quasi-poly(n,s) and outputs a generalized ΣΠΣ(k) circuit computing f. The size s includes the bit complexity of coefficients appearing in the circuit: this is the max bit complexity if the field is ℝ or ℂ, and log|F| if the field is finite.
Depth-3 circuits of constant fan-in (ΣΠΣ(k) circuits) and closely related models have been very well studied in the context of polynomial identity testing (PIT). In this paper, we build upon the structural results for identically zero ΣΠΣ(k) circuits that were studied in the context of PIT. Using connections to discrete geometry, we prove new structural properties of vanishing spaces of polynomials computed by such circuits.
Prior to our work, the only subexponential reconstruction algorithm for ΣΠΣ(k) circuits is by [Karnin–Shpilka, CCC 2009]. However, the run time is quasipolynomial in |F|, and hence this is only efficient over small finite fields. Over general (potentially exponentially large size) finite fields, efficient reconstruction algorithms were only known for k=2 ([Sinha, ITCS 2022]); and over ℝ and ℂ, they were only known for k=2 ([Sinha, CCC 2016]) and k=3 ([Saraf–Shringi, CCC 2025]).

@InProceedings{STOC26p1704, author = {Shubhangi Saraf and Devansh Shringi and Narmada Varadarajan}, title = {Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-In}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1704-1715}, doi = {10.1145/3798129.3800878}, year = {2026}, } Publisher's Version Article: stoc26main-p954-p doi:10.1145/3798129.3800878

SVP_p Is Deterministically NP-Hard for All p > 2, Even to Approximate within a Factor of 2^log1-εn
Isaac M. Hair and Amit Sahai
(University of California at Santa Barbara, USA; University of California at Los Angeles, USA)
We prove that SVP_p is NP-hard to approximate within a factor of 2^{log1 − ε n}, for all constants ε > 0 and p > 2, under standard deterministic Karp reductions. This result is also the first proof that exact SVP_p is NP-hard in a finite ℓ_p norm. Hardness for SVP_p with p finite was previously only known if NP ⊈ RP, and under that assumption, hardness of approximation was only known for all constant factors. As a corollary to our main theorem, we show that under the Sliding Scale Conjecture, SVP_p is NP-hard to approximate within a small polynomial factor, for all constants p > 2.
Our proof techniques are surprisingly elementary; we reduce from a regularized PCP instance directly to the shortest vector problem by using simple gadgets related to Vandermonde matrices and Hadamard matrices.

@InProceedings{STOC26p1716, author = {Isaac M. Hair and Amit Sahai}, title = {SVP<i>_p</i> Is Deterministically NP-Hard for All p > 2, Even to Approximate within a Factor of <i>2^{log^1-εn}</i>}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1716-1727}, doi = {10.1145/3798129.3800879}, year = {2026}, } Publisher's Version Article: stoc26main-p958-p doi:10.1145/3798129.3800879

Solving Matrix Games with Near-Optimal Matvec Complexity
Ishani Karmarkar, Liam O'Carroll, and Aaron Sidford
(Stanford University, USA)
We study the problem of computing an є-approximate Nash equilibrium of a two-player, bilinear game with a bounded payoff matrix A ∈ ℝ^{m × n}, when the players’ strategies are constrained to lie in simple sets. We provide algorithms which solve this problem in Õ(є^−2/3) matrix-vector multiplies (matvecs) in two well-studied cases: ℓ₁-ℓ₁ (or zero-sum) games, where the players’ strategies are both in the probability simplex, and ℓ₂-ℓ₁ games (encompassing hard-margin SVMs), where the players’ strategies are in the unit Euclidean ball and probability simplex respectively. These results improve upon the previous state-of-the-art complexities of Õ(є^−8/9) for ℓ₁-ℓ₁ and Õ(є^−7/9) for ℓ₂-ℓ₁ due to [KOS ’25]. In both settings our results are nearly-optimal as they match lower bounds of [KS ’25] up to polylogarithmic factors.

@InProceedings{STOC26p1728, author = {Ishani Karmarkar and Liam O'Carroll and Aaron Sidford}, title = {Solving Matrix Games with Near-Optimal Matvec Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1728-1738}, doi = {10.1145/3798129.3800880}, year = {2026}, } Publisher's Version Article: stoc26main-p975-p doi:10.1145/3798129.3800880

Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling
Jason M. Altschuler, Sinho Chewi, and Matthew S. Zhang
(University of Pennsylvania, USA; Yale University, USA; University of Toronto, Canada)
Acceleration is a celebrated cornerstone of convex optimization, enabling gradient-based algorithms to converge sublinearly in the condition number. A major open question is whether an analogous acceleration phenomenon is possible for log-concave sampling. Underdamped Langevin dynamics (ULD) has long been conjectured to be the natural candidate for acceleration, but a central challenge is that its degeneracy necessitates the development of new analysis approaches, e.g., the theory of hypocoercivity. Although recent breakthroughs established ballistic acceleration for the (continuous-time) ULD diffusion via space-time Poincaré inequalities, (discrete-time) algorithmic results remain entirely open: the discretization error of existing analysis techniques dominates any continuous-time acceleration.
In this paper, we give a new coupling-based local error framework for analyzing ULD and its numerical discretizations in KL divergence. This extends the framework in Shifted Composition III from uniformly elliptic diffusions to degenerate diffusions, and shares its virtues: the framework is user-friendly, applies to sophisticated discretization schemes, and does not require contractivity. Applying this framework to the randomized midpoint discretization of ULD establishes the first ballistic acceleration result for log-concave sampling (i.e., sublinear dependence on the condition number). Along the way, we also obtain the first d^1/3 iteration complexity guarantee for sampling to constant total variation error in dimension d.

@InProceedings{STOC26p1739, author = {Jason M. Altschuler and Sinho Chewi and Matthew S. Zhang}, title = {Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1739-1750}, doi = {10.1145/3798129.3800881}, year = {2026}, } Publisher's Version Article: stoc26main-p984-p doi:10.1145/3798129.3800881

Nonuniform Graph Partitioning with Just a Little Flex
Neil Olver, Harald Räcke, and Stefan Schmid
(London School of Economics and Political Science, UK; TU Munich, Germany; TU Berlin, Germany; Fraunhofer SIT, Germany)
In the nonuniform graph partitioning problem, we are given a capacitated graph G on n vertices, and numbers n₁, n₂, …, n_k summing to n. The goal is to partition the vertices of G into parts S₁, S₂, …, S_k with |S_i| = n_i for each i, and minimizing the capacity of edges crossing between distinct parts. This generalizes, for instance, the well-known graph bisection problem.
In order to obtain meaningful results, it is necessary to consider a bicriteria approximation, where we allow part sizes to be violated by a multiplicative factor є (i.e., |S_i| ≤ (1 + є) n_i for each i). If all part sizes are equal — uniform graph partitioning — an O(logn) approximation is possible for any constant є > 0, via a dynamic programming approach. But for nonuniform graph partitioning, no results were known without a substantial violation factor, the best result being an O(√lognlogk) approximation with є ≈ 5.
Existing approaches to nonuniform graph partitioning seem to inherently rely on at least a factor 2 violation; whereas the dynamic programming approach for uniform graph partitioning do not extend. In this paper we take a completely different approach to give the first results for arbitrary small violation, showing an O(logn/є) approximation for any constant є > 0. Our approach involves a number of novel ingredients: a refinement of Räcke decomposition trees; a ”compression scheme” to decrease certain search spaces to polynomial size; a strong linear program based around local consistency within large neighborhoods; and a rounding scheme for this LP.

@InProceedings{STOC26p1751, author = {Neil Olver and Harald Räcke and Stefan Schmid}, title = {Nonuniform Graph Partitioning with Just a Little Flex}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1751-1762}, doi = {10.1145/3798129.3800882}, year = {2026}, } Publisher's Version Article: stoc26main-p989-p doi:10.1145/3798129.3800882

Rigorous Implications of the Low-Degree Heuristic
Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, and Stefan Tiegel
(Massachusetts Institute of Technology, USA; University of California at San Diego, USA; Princeton University, USA; University of Washington, USA; Northwestern University, USA)
Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such results rely on the hypothesis that if the low-degree moments of the planted and null distributions are sufficiently close, then no efficient (noise-tolerant) algorithm should be able to distinguish between them. This hypothesis is appealing due to the simplicity of calculating the low-degree likelihood ratio (LDLR), a quantity that measures the similarity between low-degree moments. However, despite sustained interest in the area, it remains unclear whether low-degree indistinguishability actually rules out any interesting class of algorithms.
In this work, we initiate the study and develop technical tools for translating LDLR upper bounds into rigorous lower bounds against concrete algorithms. As a consequence, for any permutation-invariant distribution P, we prove:
1.) If is over {0,1}ⁿ and is low-degree indistinguishable from U = ({0,1}ⁿ), then a noisy version of is statistically indistinguishable from U.
2.) If is over ⁿ and is low-degree indistinguishable from the standard Gaussian (0, 1)ⁿ, then no statistic based on symmetric polynomials of degree at most O(logn/loglogn) can distinguish between a noisy version of from (0, 1)ⁿ.
3.) If is over ^{n× n} and is low-degree indistinguishable from (0,1)^{n× n}, then no constant-sized subgraph statistic can distinguish between a noisy version of and (0, 1)^{n× n}.
To obtain our results, we depart significantly from techniques typically used in the context of low-degree lower bounds. Instead, we show total variation closeness by carefully analyzing the Fourier transform of polynomials under the input distributions.

@InProceedings{STOC26p1763, author = {Jun-Ting Hsieh and Daniel M. Kane and Pravesh K. Kothari and Jerry Li and Sidhanth Mohanty and Stefan Tiegel}, title = {Rigorous Implications of the Low-Degree Heuristic}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1763-1770}, doi = {10.1145/3798129.3800883}, year = {2026}, } Publisher's Version Article: stoc26main-p995-p doi:10.1145/3798129.3800883

The Power of Two Bases: Robust and Copy-Optimal Certification of Nearly All Quantum States with Few-Qubit Measurements
Andrea Coladangelo, Jerry Li, Joseph Slote, and Ellen Wu
(University of Washington, USA; Massachusetts Institute of Technology, USA)
A central task in quantum information science is state certification: testing whether an unknown state is є₁-close to a fixed target state, or є₂-far. Recent work has shown that surprisingly simple measurement protocols – comprising only single-qubit measurements – suffice to certify arbitrary n-qubit states. However, these certification protocols are not robust: rather than allowing constant є₁, they can only positively certify states within є₁=O(1/n) trace distance of the target. In many experimental settings, the appropriate error tolerance is constant as the system size grows, so this lack of robustness renders existing tests inapplicable at scale, no matter how many times the test is repeated.
Here we present robust certification protocols based on few-qubit measurements that apply to all but a O(2⁻ⁿ)-fraction of pure target states. Our first protocol achieves constant robustness, i.e є₁=Θ(1), using a single O(logn)-qubit measurement along with single-qubit measurements in the Z or X basis on the other qubits. As a corollary of its robustness, this protocol also achieves constant (in n) copy complexity, which is optimal. Our second protocol uses exclusively single-qubit measurements and is nearly robust: є₁=Ω(1/logn). Our tests are based on a new uncertainty principle for conditional fidelities which may be of independent interest.

@InProceedings{STOC26p1771, author = {Andrea Coladangelo and Jerry Li and Joseph Slote and Ellen Wu}, title = {The Power of Two Bases: Robust and Copy-Optimal Certification of Nearly All Quantum States with Few-Qubit Measurements}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1771-1776}, doi = {10.1145/3798129.3800884}, year = {2026}, } Publisher's Version Article: stoc26main-p999-p doi:10.1145/3798129.3800884

Optimal Phylogenetic Reconstruction from Sampled Quartets
Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, and Konstantin Makarychev
(Northwestern University, USA; University of California at Santa Cruz, USA)
Quartet Reconstruction, the task of recovering a single phylogenetic tree from smaller trees on four species called quartets, is a well-studied problem in theoretical computer science with far-reaching connections to biology, statistics and graph theory. Given a random sample containing m noisy quartets, labeled according to an unknown ground-truth tree T on n taxa, we want to learn the tree structure of T with small generalization error, i.e., to output a tree T that is close to T in terms of quartet distance and can predict the classification of unseen quartets. Unfortunately, the empirical risk minimizer corresponds to the NP-hard problem of finding a tree that maximizes agreements with the sampled quartets, and earlier works in approximation algorithms gave (1−є)-approximation schemes (PTAS) for dense instances with m=Θ(n⁴) quartets, or for m=Θ(n²logn) quartets randomly sampled from T.
Prior to our work, it was unknown how many samples are information-theoretically required to learn the tree, and whether there is an efficient reconstruction algorithm. We present optimal results for reconstructing an unknown phylogenetic tree T from a random sample of m=Θ(n) quartets, potentially corrupted under the standard Random Classification Noise (RCN) model. This matches the Ω(n) lower bound required for any meaningful tree reconstruction, as for m=o(n), large parts of T cannot be recovered, and exact tree reconstruction (є=0) requires Ω(n³) quartets. Our contribution is twofold: first, we give a tree reconstruction algorithm that, not only achieves a (1−є)-approximation for Quartet Reconstruction, but most importantly recovers a tree close to T in quartet distance; second, we show a new Θ(n) bound on the Natarajan dimension of phylogenies (an analog of VC dimension in multiclass classification), which may be of independent interest. Coupled together, these imply that our reconstructed tree T will generalize well to unseen quartets. Our analysis relies on a new Quartet-based Embedding and Detection (QED) procedure, that repeatedly identifies and removes well-clustered subtrees from the (unknown) ground-truth T via semidefinite programming.

@InProceedings{STOC26p1777, author = {Dionysis Arvanitakis and Vaggos Chatziafratis and Yiyuan Luo and Konstantin Makarychev}, title = {Optimal Phylogenetic Reconstruction from Sampled Quartets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1777-1788}, doi = {10.1145/3798129.3800885}, year = {2026}, } Publisher's Version Article: stoc26main-p1059-p doi:10.1145/3798129.3800885

High Rate Efficient Local List Decoding from HDX
Yotam Dikstein, Max Hopkins, Toniann Pitassi, and Russell Impagliazzo
(Institute for Advanced Study at Princeton, USA; Princeton University, USA; Columbia University, USA; University of California at San Diego, USA)
We construct the first (locally computable, approximately) locally list decodable codes with rate, efficiency, and error tolerance approaching the information theoretic limit, a core regime of interest for the complexity theoretic task of hardness amplification. Our algorithms run in polylogarithmic time and sub-logarithmic depth, which together with classic constructions in the unique decoding (low-noise) regime leads to the resolution of several long-standing problems in coding and complexity theory:
1. Near-optimally input-preserving hardness amplification (and corresponding fast PRGs) 2. Constant rate codes with log(N)-depth list decoding (RNC¹) 3. Complexity-preserving distance amplification
Our codes are built on the powerful theory of (local-spectral) high dimensional expanders (HDX). At a technical level, we make two key contributions. First, we introduce a new framework for (poly log(N)-round) belief propagation on HDX that leverages a mix of local correction and global expansion to control error build-up while maintaining high rate. Second, we introduce the notion of strongly explicit local routing on HDX, local algorithms that given any two target vertices, output a random path between them in only polylogarithmic time (and, preferably, sub-logarithmic depth). Constructing such schemes on certain coset HDX allows us to instantiate our otherwise combinatorial framework in polylogarithmic time and low depth, completing the result.

@InProceedings{STOC26p1789, author = {Yotam Dikstein and Max Hopkins and Toniann Pitassi and Russell Impagliazzo}, title = {High Rate Efficient Local List Decoding from HDX}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1789-1799}, doi = {10.1145/3798129.3800886}, year = {2026}, } Publisher's Version Article: stoc26main-p1064-p doi:10.1145/3798129.3800886