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

Title Page


Article: stoc26foreword-fm000-p

Welcome from the Chairs


Article: stoc26foreword-fm001-p

STOC 2026 Organization


Article: stoc26foreword-fm002-p

Sponsors


Article: stoc26foreword-fm003-p

Lower Bounds against the Ideal Proof System in Finite Fields
Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, and Iddo Tzameret
(Imperial College London, UK)


Article Search Article: stoc26main-p4-p

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
Jason Li
(Carnegie Mellon University, USA)


Article Search Article: stoc26main-p8-p

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)


Article Search Article: stoc26main-p21-p

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)


Article Search Article: stoc26main-p24-p

Smoothed Analysis of Learning from Positive Samples
Jane Lee, Anay Mehrotra, and Manolis Zampetakis
(Yale University, USA)


Article Search Article: stoc26main-p25-p

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)


Article Search Article: stoc26main-p26-p

Separator Theorem for Minor-Free Graphs in Linear Time
Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, and Tomáš Masařík
(CNRS, France; University of Copenhagen, Denmark; University of Massachusetts at Amherst, USA; Carnegie Mellon University, USA; University of Warsaw, Poland)


Article Search Article: stoc26main-p31-p

Near Optimal Hardness of Approximating 𝑘-CSP
Dor Minzer and Kai Zhe Zheng
(Massachusetts Institute of Technology, USA)


Article Search Article: stoc26main-p34-p

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, USA)


Article Search Article: stoc26main-p38-p

A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning Conjunctions
Xi Chen, Shyamal Patel, and Rocco A. Servedio
(Columbia University, USA)


Article Search Article: stoc26main-p48-p

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.

Article Search Article: stoc26main-p52-p

Almost-Optimal Approximation Algorithm for Global Minimum Cut in Directed Graphs
Ron Mosenzon
(Toyota Technological Institute at Chicago, USA)


Article Search Article: stoc26main-p53-p

Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method
Yang 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].

Preprint Info Article: stoc26main-p55-p

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.

Article Search Article: stoc26main-p56-p

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)


Article Search Article: stoc26main-p65-p

Compressed Permutation Oracles
Joseph Carolan
(University of Maryland at College Park, USA)


Article Search Article: stoc26main-p68-p

Optimal Contest beyond Convexity
Negin Golrezaei, MohammadTaghi Hajiaghayi, and Suho Shin
(Massachusetts Institute of Technology, USA; University of Maryland, USA)


Article Search Article: stoc26main-p69-p

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)


Article Search Article: stoc26main-p81-p

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)


Article Search Article: stoc26main-p85-p

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)


Article Search Article: stoc26main-p87-p

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)


Article Search Article: stoc26main-p98-p

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)


Article Search Article: stoc26main-p103-p

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)


Article Search Article: stoc26main-p108-p

A Dichotomy Theorem for Multi-pass Streaming CSPs
Yumou Fei, Dor Minzer, and Shuo Wang
(Massachusetts Institute of Technology, USA)


Article Search Article: stoc26main-p111-p

NP-Membership for the Boundary-Boundary Art-Gallery Problem
Jack Stade
(University of Copenhagen, Denmark)


Article Search Article: stoc26main-p120-p

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)


Article Search Article: stoc26main-p125-p

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)


Article Search Article: stoc26main-p127-p

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)


Article Search Article: stoc26main-p138-p

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)


Article Search Article: stoc26main-p148-p

Fourier Spectrum of Noisy Quantum Algorithms
Uma Girish
(Columbia University, USA)


Article Search Article: stoc26main-p157-p

MIPco=coRE
Junqiao (Randy) Lin
(CWI, Netherlands; QuSoft, Netherlands)


Article Search Article: stoc26main-p163-p

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

Article Search Article: stoc26main-p169-p

Fine-Grained Complexity of Continuous Euclidean k-Center
Lotte Blank, Karl Bringmann, Parinya Chalermsook, Karthik C. S., Benedikt Kolbe, Hung Le, and Geert van Wordragen
(University of Bonn, Germany; Saarland University, Germany; MPI-INF, Germany; University of Sheffield, UK; Rutgers University, USA; University of Massachusetts at Amherst, USA; Aalto University, Finland)


Article Search Article: stoc26main-p171-p

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)


Article Search Article: stoc26main-p175-p

A Sharp Characterization of Pessiland
Shuichi Hirahara and Mikito Nanashima
(National Institute of Informatics, Tokyo, Japan; Institute of Science Tokyo, Japan)


Article Search Article: stoc26main-p177-p

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)


Article Search Article: stoc26main-p178-p

Complexity-Theoretic Universal Inductive Inference
Shuichi Hirahara and Mikito Nanashima
(National Institute of Informatics, Tokyo, Japan; Institute of Science Tokyo, Japan)


Article Search Article: stoc26main-p181-p

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)


Article Search Article: stoc26main-p183-p

Instance-Optimal Quantum State Certification with Entangled Measurements
Ryan O'Donnell and Chirag Wadhwa
(Carnegie Mellon University, USA; University of Edinburgh, UK)


Article Search Article: stoc26main-p187-p

Hesse’s Redemption: Efficient Convex Polynomial Programming
Lucas Slot, David Steurer, and Manuel Wiedmer
(ETH Zurich, Switzerland)


Article Search Article: stoc26main-p193-p

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: <ul> <li><strong>A “Junta Theorem” for Norms:</strong> 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). </li> <li><strong>Sparsification of Convex Sets:</strong> 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. </li> </ul>

Article Search Article: stoc26main-p202-p

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)


Article Search Article: stoc26main-p206-p

Derandomizing Matrix Concentration Inequalities from Free Probability
Robert Wang, Lap Chi Lau, and Hong Zhou
(University of Waterloo, Canada; Fuzhou University, China)


Article Search Article: stoc26main-p209-p

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)


Article Search Article: stoc26main-p217-p

A Constant-Factor Approximation for Directed Latency
Jannis Blauth and Ramin Mousavi
(ETH Zurich, Switzerland; IDSIA at USI-SUPSI, Switzerland)


Article Search Article: stoc26main-p221-p

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)


Article Search Article: stoc26main-p226-p

The Complexity of Min-Max Optimization with Product Constraints
Martino Bernasconi and Matteo Castiglioni
(Bocconi University, Italy; Politecnico di Milano, Italy)


Article Search Article: stoc26main-p227-p

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)


Article Search Article: stoc26main-p234-p

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)


Article Search Article: stoc26main-p245-p

Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time
Mehrdad Ghadiri, Junzhao Yang, and Angelo Farfan
(Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA)


Article Search Article: stoc26main-p247-p

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)


Article Search Article: stoc26main-p250-p

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)


Article Search Article: stoc26main-p255-p

Optimal Random Self-Reductions for All Linear Problems
Shuichi Hirahara and Nobutaka Shimizu
(National Institute of Informatics, Tokyo, Japan; Institute of Science Tokyo, Japan)


Article Search Article: stoc26main-p264-p

Determination of the Fifth Busy Beaver Value
The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev (Skelet), Rachel Hunter, Matthew L. House, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, and Théo Zimmermann
(bbchallenge.org, USA; None, USA; Inria Paris, France; Sofia University, Bulgaria; University of Warsaw, Poland; PRGM DEV, USA; University of California at San Diego, USA; LTCI - Télécom Paris - Institut Polytechnique de Paris, France)


Article Search Article: stoc26main-p268-p

Dynamic Meta-Kernelization
Christian Bertram, Deborah Haun, Mads Vestergaard Jensen, and Tuukka Korhonen
(University of Copenhagen, Denmark; KIT, Germany)


Article Search Article: stoc26main-p269-p

Boolean Function Monotonicity Testing Requires (Almost) n^1/2 Queries
Mark Chen, Xi Chen, Hao Cui, William Pires, and Jonah Stockwell
(Columbia University, USA)


Article Search Article: stoc26main-p270-p

Separating QMA from QCMA with a Classical Oracle
John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, and Mark Zhandry
(Columbia University, USA; Saarland University, Germany; University of Washington, USA; NTT Research, USA; Stanford University, USA)


Article Search Article: stoc26main-p275-p

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.

Article Search Article: stoc26main-p277-p

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)


Article Search Article: stoc26main-p281-p

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)


Article Search Article: stoc26main-p286-p

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)


Article Search Article: stoc26main-p288-p

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)


Article Search Article: stoc26main-p292-p

SNARGs for NP and Non-signaling PCPs, Revisited
Lalita Devadas, Samuel B. Hopkins, Yael Kalai, Pravesh K. Kothari, Alex Lombardi, and Surya Mathialagan
(Massachusetts Institute of Technology, USA; Princeton University, USA; NTT Research, USA)


Article Search Article: stoc26main-p297-p

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)


Article Search Article: stoc26main-p298-p

Fast and Compact Random Mappings with Uniform Guarantees and Applications
Ying Feng and Piotr Indyk
(Massachusetts Institute of Technology, USA)


Article Search Article: stoc26main-p303-p

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)


Article Search Article: stoc26main-p304-p

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)


Article Search Article: stoc26main-p305-p

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)


Article Search Article: stoc26main-p308-p

Quantum Circuit Lower Bounds in the Magic Hierarchy
Natalie Parham
(Columbia University, USA)


Article Search Article: stoc26main-p310-p

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
Xiao Mao and Aviad Rubinstein
(Stanford University, USA)


Article Search Article: stoc26main-p322-p

Trust Region Interior Point Methods: Optimal L2- 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)


Article Search Article: stoc26main-p331-p

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)


Article Search Article: stoc26main-p335-p

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)


Article Search Article: stoc26main-p342-p

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)


Article Search Article: stoc26main-p343-p

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)


Article Search Article: stoc26main-p348-p

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)


Article Search Article: stoc26main-p352-p

Average Hardness of SIVP for Module Lattices of Fixed Rank
Koen de Boer, Aurel Page, Radu Toma, and Benjamin Wesolowski
(Unaffiliated, France; 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)


Article Search Article: stoc26main-p353-p

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)


Article Search Article: stoc26main-p360-p

Fast Mixing of Quantum Spin Chains at All Temperatures
Thiago Bergamaschi and Chi-Fang Chen
(University of California at Berkeley, USA)


Article Search Article: stoc26main-p363-p

Magic and Communication Complexity
Uma Girish, Alex May, Natalie Parham, and Henry Yuen
(Columbia University, USA; Perimeter Institute for Theoretical Physics, Canada)


Article Search Article: stoc26main-p364-p

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)


Article Search Article: stoc26main-p373-p

Clifford Testing: Algorithms and Lower Bounds
Marcel Hinsche, Zongbo Bao, Phillipe van Dordrecht, Jens Eisert, Jop Briet, and Jonas Helsen
(FU Berlin, Germany; CWI, Netherlands; QuSoft, Netherlands)


Article Search Article: stoc26main-p379-p

Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits
Lijie Chen, Avishay Tal, and Yichuan Wang
(University of California at Berkeley, USA)


Article Search Article: stoc26main-p385-p

Deterministic Hardness of Approximation of Unique-SVP and GapSVP in ℓ_p Norms for p<2
Yahli Hecht and Muli Safra
(Tel Aviv University, Israel)


Article Search Article: stoc26main-p388-p

Strong ETH Holds for Bounded-Depth Resolution over Parities
Klim Efremenko and Dmitry Itsykson
(Ben-Gurion University of the Negev, Israel)


Article Search Article: stoc26main-p393-p

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
Sayan Bhattacharya, Ruoxu Cen, and Debmalya Panigrahi
(University of Warwick, UK; Duke University, USA)


Article Search Article: stoc26main-p395-p

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
Nick Fischer
(MPI-INF, Germany)


Article Search Article: stoc26main-p396-p

Can Like Attract Like? A Study of Homonymous Gathering in Networks
Yoann Dieudonné, Stéphane Devismes, and Arnaud Labourel
(MIS - Université de Picardie Jules Verne, France; LIS - Aix-Marseille University, France)


Article Search Article: stoc26main-p403-p

Steiner Forest: A Simplified Better-Than-2 Approximation
Anupam Gupta and Vera Traub
(New York University, USA; ETH Zurich, Switzerland)


Article Search Article: stoc26main-p404-p

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)


Article Search Article: stoc26main-p416-p

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)


Article Search Article: stoc26main-p428-p

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)


Article Search Article: stoc26main-p429-p

Zero-Free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma Regime
Jingcheng Liu and Yixiao Yu
(Nanjing University, China)


Article Search Article: stoc26main-p435-p

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, Chennai, India; IIT Jodhpur, India; Ben-Gurion University of the Negev, Israel; University of Bergen, Norway; Institute of Mathematical Sciences, India)


Article Search Article: stoc26main-p443-p

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)


Article Search Article: stoc26main-p454-p

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)


Article Search Article: stoc26main-p460-p

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)


Article Search Article: stoc26main-p470-p

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)


Article Search Article: stoc26main-p474-p

Space-Efficient Dictionary Matching with Mismatches using Function Inversion
Jackson Bibbens, Levi Borevitz, and Samuel McCauley
(University of Massachusetts at Amherst, USA; Northwestern University, USA; Williams College, USA)


Article Search Article: stoc26main-p480-p

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)


Article Search Article: stoc26main-p482-p

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)


Article Search Article: stoc26main-p487-p

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)


Article Search Article: stoc26main-p505-p

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'ozy (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.

Preprint Article: stoc26main-p510-p

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)


Article Search Article: stoc26main-p516-p

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)


Article Search Article: stoc26main-p518-p

Constructive Approximation under Carleman’s Condition, with Applications to Smoothed Analysis
Frederic Koehler and Beining Wu
(University of Chicago, USA)


Article Search Article: stoc26main-p521-p

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)


Article Search Article: stoc26main-p522-p

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)


Article Search Article: stoc26main-p523-p

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)


Article Search Article: stoc26main-p524-p

Efficient Reversal of Transductions of Sparse Graph Classes
Jakub Gajarský, Michał Pilipczuk, and Jan Dreier
(University of Warsaw, Poland; TU Wien, Austria)


Article Search Article: stoc26main-p530-p

Markov Chains Approximate Message Passing
Amit Rajaraman and David X. Wu
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)


Article Search Article: stoc26main-p535-p

Online Combinatorial Optimization with Graphical Dependencies
Zhimeng Gao, Evangelia Gergatsouli, Kalen Patton, and Sahil Singla
(Georgia Institute of Technology, USA)


Article Search Article: stoc26main-p545-p

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)


Article Search Article: stoc26main-p548-p

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)


Article Search Article: stoc26main-p551-p

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)


Article Search Article: stoc26main-p565-p

Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
Aviad Rubinstein and Sahil Singla
(Stanford University, USA; Georgia Institute of Technology, USA)


Article Search Article: stoc26main-p569-p

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
Yotam Kenneth-Mordoch and Robert Krauthgamer
(Weizmann Institute of Science, Israel)


Article Search Article: stoc26main-p571-p

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)


Article Search Article: stoc26main-p589-p

Hardness Amplification beyond Boolean Functions
Nobutaka Shimizu and Kenji Yasunaga
(Institute of Science Tokyo, Japan)


Article Search Article: stoc26main-p590-p

Compressing Dynamic Fully Indexable Dictionaries in Word-RAM
Gabriel Marques Domingues
(Tel Aviv University, Israel)


Article Search Article: stoc26main-p594-p

The Price of Competitive Information Disclosure
Sid Banerjee, Kamesh Munagala, Yiheng Shen, and Kangning Wang
(Cornell University, USA; Duke University, USA; Rutgers University, USA)


Article Search Article: stoc26main-p601-p

Beating Meet-in-the-Middle for Subset Balancing Problems
Tim Randolph and Karol Węgrzycki
(Harvey Mudd College, USA; MPI-INF, Germany)


Article Search Article: stoc26main-p606-p

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)


Article Search Article: stoc26main-p624-p

The Natural Proofs Barrier against Data-Structure Lower-Bounds
Bruno Loff, Michal Koucký, Tulasimohan Molli, and Michael E. Saks
(LASIGE, Portugal; University of Lisbon, Portugal; Charles University, Czech Republic; Rutgers University, USA)


Article Search Article: stoc26main-p628-p

Extractors for Samplable Distributions from the Two-Source Extractor Recipe
Justin Oh and Ronen Shaltiel
(University of Haifa, Israel)


Article Search Article: stoc26main-p633-p

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)


Article Search Article: stoc26main-p634-p

Lower Bounds on Flow Sparsifiers with Steiner Nodes
Yu Chen, Zihan Tan, and Mingyang Yang
(National University of Singapore, Singapore; University of Minnesota, USA)


Article Search Article: stoc26main-p636-p

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)


Article Search Article: stoc26main-p656-p

A Graph Minors Approach to Temporal Sequences
Johannes Carmesin and William Turner
(TU Bergakademie Freiberg, Germany)


Article Search Article: stoc26main-p668-p

What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing
Lelia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca
(Université Paris Cité - IRIF - CNRS, France; University of Bergen, Norway; CNRS - Université de Paris, France; École Normale Supérieure, France; Universidad Adolfo Ibáñez, Chile; Universidad de Chile, Chile; Université d'Orléans, France)


Article Search Article: stoc26main-p673-p

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)


Article Search Article: stoc26main-p674-p

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)


Article Search Article: stoc26main-p678-p

Near-Optimal Directed Euclidean Spanners in High Dimensions
Rajesh Jayaram, Shyamal Patel, Cliff Stein, Erik Waingarten, and Tian Zhang
(Google Research, USA; Columbia University, USA; University of Pennsylvania, USA)


Article Search Article: stoc26main-p703-p

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)


Article Search Article: stoc26main-p713-p

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)


Article Search Article: stoc26main-p715-p

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)


Article Search Article: stoc26main-p718-p

Approximate Orthogonal Vectors and Diameter via Regularity Lemma
Alexandr Andoni, Shunhua Jiang, and Stepan Zharkov
(Columbia University, USA; Hebrew University of Jerusalem, Israel)


Article Search Article: stoc26main-p734-p

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)


Article Search Article: stoc26main-p741-p

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)


Article Search Article: stoc26main-p775-p

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)


Article Search Article: stoc26main-p776-p

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)


Article Search Article: stoc26main-p777-p

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.

Article Search Article: stoc26main-p778-p

Approximating Directed Connectivity in Almost-Linear Time
Kent Quanrud
(Purdue University, USA)


Article Search Article: stoc26main-p791-p

An Optimal Algorithm for Stochastic Vertex Cover
Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Cliff 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)


Article Search Article: stoc26main-p798-p

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)


Article Search Article: stoc26main-p809-p

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)


Article Search Article: stoc26main-p813-p

Learning Functions of Halfspaces
Josh Alman, Shyamal Patel, and Rocco A. Servedio
(Columbia University, USA)


Article Search Article: stoc26main-p827-p

Failure of Symmetry of Information for Randomized Computations
Jinqiao Hu, Yahel Manor, and Igor C. Oliveira
(University of Warwick, UK; University of Haifa, Israel)


Article Search Article: stoc26main-p834-p

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
Julia Chuzhoy, Sanjeev Khanna, and Junkai Song
(Toyota Technological Institute at Chicago, USA; University of Pennsylvania, USA)


Article Search Article: stoc26main-p840-p

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
Sitan Chen, Jingqiu Ding, Mahbod Majid, and Walt McKelvie
(Harvard University, USA; ETH Zurich, Switzerland; Massachusetts Institute of Technology, USA)


Article Search Article: stoc26main-p850-p

Sub-linear Secure Broadcast and Applications
Yuval Gelles, Ilan Komargodski, and Merav Parter
(Hebrew University of Jerusalem, Israel; Weizmann Institute of Science, Israel)


Article Search Article: stoc26main-p851-p

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)


Article Search Article: stoc26main-p859-p

Settling the Pass Complexity of Streaming Set Cover
Sepehr Assadi and Janani Sundaresan
(University of Waterloo, Canada)


Article Search Article: stoc26main-p871-p

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)


Article Search Article: stoc26main-p879-p

Reach Unambiguous Logspace Is Almost in Logspace
V. Arvind and Samir Datta
(Institute of Mathematical Sciences, Chennai, India; Chennai Mathematical Institute, India)


Article Search Article: stoc26main-p905-p

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 Kanpur, India; ISI Kolkata, India; IIT Bombay, India; Tata Institute of Fundamental Research, Mumbai, India)


Article Search Article: stoc26main-p909-p

Language Generation and Identification from Partial Enumeration: Tight Density Bounds and Topological Characterizations
Jon Kleinberg and Fan Wei
(Cornell University, USA; Duke University, USA)


Article Search Article: stoc26main-p926-p

Approximation Algorithms for Satisfiable and Nearly Satisfiable Ordering CSPs
Yury Makarychev
(Toyota Technological Institute at Chicago, USA)


Article Search Article: stoc26main-p928-p

Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-In
Shubhangi Saraf, Devansh Shringi, and Narmada Varadarajan
(University of Toronto, Canada)


Article Search Article: stoc26main-p954-p

SVP_p Is 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)


Article Search Article: stoc26main-p958-p

Solving Matrix Games with Near-Optimal Matvec Complexity
Ishani Karmarkar, Liam O'Carroll, and Aaron Sidford
(Stanford University, USA)


Article Search Article: stoc26main-p975-p

Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling
Jason M. Altschuler, Sinho Chewi, and Matthew (Shunshi) Zhang
(University of Pennsylvania, USA; Yale University, USA; University of Toronto, Canada)


Article Search Article: stoc26main-p984-p

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)


Article Search Article: stoc26main-p989-p

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)


Article Search Article: stoc26main-p995-p

The Power of Two Bases: Nearly Robust and Copy-Optimal Certification of Nearly All Quantum States with Single-Qubit Measurements
Andrea Coladangelo, Jerry Li, Joseph Slote, and Ellen Wu
(University of Washington, USA; Massachusetts Institute of Technology, USA)


Article Search Article: stoc26main-p999-p

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)


Article Search Article: stoc26main-p1059-p

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)


Article Search Article: stoc26main-p1064-p

First-Order (Coarse) Correlated Equilibria in Non-concave Games
Mete Şeref Ahunbay
(CNRS - Université Grenoble Alpes - INRIA - LIG, France)


Article Search Article: stoc26main-p1080-p

SNARKs from LWE via Non-black-Box Reductions
Zhengzhong Jin, Mingqi Lu, and Bo Peng
(Northeastern University, USA; Peking University, China)


Article Search Article: stoc26main-p1088-p

A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
Gautam Chandrasekaran, Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan
(University of Texas at Austin, USA)


Article Search Article: stoc26main-p1095-p

Shuffling Is Universal: Statistical Additive Randomized Encodings for All Functions
Nir Bitansky, Saroja Erabelli, Rachit Garg, and Yuval Ishai
(New York University, USA; Technion, Israel; AWS, USA)


Article Search Article: stoc26main-p1125-p

Testing Distributions against Bounded Distinguishers
Mark Bun, Rathin Desai, and Renato Ferreira Pinto Jr.
(Boston University, USA; Columbia University, USA)


Article Search Article: stoc26main-p1134-p

Randomized Rounding over Dynamic Programs
Étienne Bamas, Shi Li, and Lars Rohwedder
(EPFL, Switzerland; Nanjing University, China; University of Southern Denmark, Denmark)


Article Search Article: stoc26main-p1143-p

Toward Optimal Approximations for Resource-Minimization for Fire Containment on Trees and Non-uniform k-Center
Jannis Blauth, Christian Nöbel, and Rico Zenklusen
(ETH Zurich, Switzerland)


Article Search Article: stoc26main-p1150-p

A (4+ϵ)-Approximation for Euclidean 𝑘-Means via Non-monotone Dual-Fitting
Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, and Ernest van Wijland
(Stanford University, USA; Google Research, France; IDSIA at USI-SUPSI, Switzerland; University of Michigan, USA; Université Paris-Cité - CNRS, France)


Article Search Article: stoc26main-p1152-p

Restriction Trees for Sparsity and Applications
Arkadev Chattopadhyay, Yogesh Dahiya, and Shachar Lovett
(Tata Institute of Fundamental Research, Mumbai, India; University of California at San Diego, USA)


Article Search Article: stoc26main-p1195-p

On the Need for (Quantum) Memory with Short Outputs
Zihan Hao, Qipeng Liu, and Zikuan Huang
(University of California at San Diego, USA; Tsinghua University, China)


Article Search Article: stoc26main-p1237-p

Monte Carlo to Las Vegas for Recursively Composed Functions
Bandar Al-Dhalaan and Shalev Ben David
(University of Waterloo, Canada)


Article Search Article: stoc26main-p1245-p

Range Avoidance, Arthur-Merlin, and TFNP
Surendra Ghentiyala, Zeyong Li, and Noah Stephens-Davidowitz
(Cornell University, USA; National University of Singapore, Singapore)


Article Search Article: stoc26main-p1260-p

Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
Maxime Flin, Magnús Halldórsson, Manuel Jakob, and Yannic Maus
(Aalto University, Finland; Reykjavik University, Iceland; TU Graz, Austria)


Article Search Article: stoc26main-p1266-p

Learning Stabilizer Structure of Quantum States
Srinivasan Arunachalam and Arkopal Dutt
(IBM Research, USA)


Article Search Article: stoc26main-p1268-p

A Unified Framework for Analysis of Randomized Greedy Matching Algorithms
Mahsa Derakhshan and Tao Yu
(Northeastern University, USA)


Article Search Article: stoc26main-p1274-p

From Hop Reduction to Sparsification for Negative Length Shortest Paths
Kent Quanrud and Navid Tajkhorshid
(Purdue University, USA; University of Illinois at Urbana-Champaign, USA)


Article Search Article: stoc26main-p1292-p

Learning Mixture Models via Efficient High-Dimensional Sparse Fourier Transforms
Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li, and Manolis Zampetakis
(Yale University, USA; Princeton University, USA)


Article Search Article: stoc26main-p1321-p

Combinatorial Optimization using Comparison Oracles
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Pittu, Jon Schneider, and David P. Woodruff
(Google Research, New-York, USA; Bocconi University, Italy; New York University, USA; Google Research, USA; University of Michigan, USA; Duke University, USA; Carnegie Mellon University, USA)


Article Search Article: stoc26main-p1341-p

Computational and Statistical Lower Bounds for Low-Rank Estimation under General Inhomogeneous Noise
Debsurya De and Dmitriy Kunisky
(Johns Hopkins University, USA)


Article Search Article: stoc26main-p1352-p

Secret-Key PIR from Random Linear Codes
Caicai Chen, Yuval Ishai, Tamer Mour, and Alon Rosen
(Bocconi University, Italy; Technion, Israel; AWS, USA)


Article Search Article: stoc26main-p1368-p

Pseudodeterministic Communication Complexity
Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan
(EPFL, Switzerland; University of British Columbia, Canada; Université de Montréal, Canada)


Article Search Article: stoc26main-p1390-p

Deterministic List Decoding of Reed-Solomon Codes
Soham Chatterjee, Mrinal Kumar, and Prahladh Harsha
(Tata Institute of Fundamental Research, Mumbai, India)


Article Search Article: stoc26main-p1402-p

Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
Xiaohui Bei, Yuda Feng, Yang Hu, Shi Li, and Ruilong Zhang
(Nanyang Technological University, Singapore; Nanjing University, China; Tsinghua University, China; TU Munich, Germany)


Article Search Article: stoc26main-p1408-p

The Sample Complexity of Replicable Realizable PAC Learning
Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, and Clement Svendsen
(Aarhus University, Denmark; Stanford University, USA)


Article Search Article: stoc26main-p1419-p

Negations Are Powerful Even in Small Depth
Bruno Cavalar, Théo Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, and Amir Yehudayoff
(University of Oxford, UK; University of Copenhagen, Denmark; Chennai Mathematical Institute, India)


Article Search Article: stoc26main-p1423-p

Improved Approximation Algorithms for Non-preemptive Throughput Maximization
Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese
(TU Munich, Germany; IDSIA at USI-SUPSI, Switzerland)


Article Search Article: stoc26main-p1425-p

Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling
Karl Bringmann, Anita Durr, and Karol Węgrzycki
(Saarland University, Germany; MPI-INF, Germany)


Article Search Article: stoc26main-p1518-p

Provable Long-Range Benefits of Next-Token Prediction
Xinyuan Cao and Santosh S. Vempala
(Georgia Institute of Technology, USA)


Article Search Article: stoc26main-p1520-p

Half-Approximating Maximum Dicut in the Streaming Setting
Amir Azarmehr, Soheil Behnezhad, Shane Ferrante, and Mohammad Saneian
(Northeastern University, USA)


Article Search Article: stoc26main-p1536-p

Improved Pseudorandom Codes from Permuted Puzzles
Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, and Daniel Wichs
(Columbia University, USA; Microsoft Research, USA; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; Northeastern University, USA)


Article Search Article: stoc26main-p1557-p

Cutting Planarians: Planar Emulators for String Graphs
Hsien-Chih Chang, Jonathan Conroy, Zihan Tan, and Da Wei Zheng
(Dartmouth College, USA; University of Minnesota, USA; IST Austria, Austria)


Article Search Article: stoc26main-p1565-p

A Poisson Process for Submodular Maximization
Amit Ganz, Ariel Kulik, Roy Schwartz, and Mohit Singh
(Technion, Israel; Ben-Gurion University of the Negev, Israel; Georgia Institute of Technology, USA)


Article Search Article: stoc26main-p1663-p

Efficient Calibration for Decision Making
Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar, and Pranay Tankala
(Apple, USA; University of Texas at Austin, USA; Harvard University, USA)


Article Search Article: stoc26main-p1666-p

A Strong Linear Programming Relaxation for Weighted Tree Augmentation
Vincent Cohen-Addad, Marina Drygala, Nathan Klein, and Ola Svensson
(Google Research, France; EPFL, Switzerland; Boston University, USA)


Article Search Article: stoc26main-p1669-p

Optimal and Efficient Partite Decompositions of Hypergraphs
Andrew Krapivin, Benjamin Przybocki, Nicolás Sanhueza-Matamala, and Bernardo Subercaseaux
(Carnegie Mellon University, USA; Universidad de Concepción, Chile)


Article Search Article: stoc26main-p1693-p

Improved Lower Bounds for QAC0
Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, and John Wright
(University of California at Berkeley, USA)


Article Search Article: stoc26main-p1703-p

Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
Guy Goldberg, Tom Gur, and Sidhant Saraogi
(Weizmann Institute of Science, Israel; University of Cambridge, UK; Georgetown University, USA)


Article Search Article: stoc26main-p1782-p

Private Learning of Littlestone Classes, Revisited
Xin Lyu
(University of California at Berkeley, USA)


Article Search Article: stoc26main-p1801-p

A Polylogarithmic Approximation for Buy-at-Bulk Network Design with Protection
Chandra Chekuri and Rhea Jain
(University of Illinois at Urbana-Champaign, USA)


Article Search Article: stoc26main-p1857-p

Sparse Linear Regression Is Easy on Random Supports
Gautam Chandrasekaran, Raghu Meka, and Konstantinos Stavropoulos
(University of Texas at Austin, USA; University of California at Los Angeles, USA)


Article Search Article: stoc26main-p1875-p

Fine-Grained Bounds for Courcelle’s Theorem
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi
(University of California Santa Barbara, USA; University of Leeds, UK; Institute of Mathematical Sciences, India; New York University Shanghai, China; Ben-Gurion University of the Negev, Israel)


Article Search Article: stoc26main-p1957-p

DAG Projections: Reducing Distance and Flow Problems to DAGs
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)


Article Search Article: stoc26main-p1972-p

Adversarial Robustness on Insertion-Deletion Streams
Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou
(Princeton University, USA; Carnegie Mellon University, USA; Texas A&M University, USA)


Article Search Article: stoc26main-p2045-p

Combinatorial Markov Search
Robin Bowers, Elias Lindgren, and Bo Waggoner
(University of Colorado Boulder, USA)


Article Search Article: stoc26main-p2089-p

Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
Aleksandar Nikolov, Haohua Tang, and Jonathan Ullman
(University of Toronto, Canada; Northeastern University, USA)


Article Search Article: stoc26main-p2157-p