STOC 2026 – Preliminary Table of Contents

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)).

Publisher's Version Article: stoc26main-p4-p doi:10.1145/3798129.3800721

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⁴)^{4^k}. 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.

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.

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.

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.

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.

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.

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.

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^{Õ(n^1/3)}, for constant excess error є. This improves on the fastest previously published algorithm, which runs in time 2^{Õ(n^1/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^{Õ(k^1/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.

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.

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.

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].

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.

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_F₂), new generators for Sherali–Adams (SA), and hardness results for circuit lower bound statements against PCR_F₂, as detailed below.
Generators for PCR_F₂. 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_F₂.
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_F₂ 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_F₂.
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.

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.

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.

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.

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.

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.

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.

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.

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.

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].

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.

Publisher's Version Article: stoc26main-p120-p doi:10.1145/3798129.3800745

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^{2^O(k⁴logk)} · 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.

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.

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.

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.

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.

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).

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(k^1−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(k^1−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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Publisher's Version Article: stoc26main-p245-p doi:10.1145/3798129.3800769

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.

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.

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.

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).

Publisher's Version

STOC 2026 – Preliminary Table of Contents

Frontmatter

Research Papers