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

Title Page

Article: stoc26foreword-fm000-p (type: Frontmatter) doi:

Welcome from the Chairs

Article: stoc26foreword-fm001-p (type: Frontmatter) doi:

STOC 2026 Organization

Article: stoc26foreword-fm002-p (type: Frontmatter) doi:

STOC 2026 Sponsors

Article: stoc26foreword-fm003-p (type: Frontmatter) doi:

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

Publisher's Version Article: stoc26main-p4-p (type: Full Paper) doi:10.1145/3798129.3800721

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

Publisher's Version Article: stoc26main-p8-p (type: Full Paper) doi:10.1145/3798129.3800722

Forbidden Subgraphs of Graphs with Low Bandwidth
Maria Chudnovsky, Daniel Lokshtanov, and Eran Nevo
(Princeton University, USA; University of California at Santa Barbara, USA; Hebrew University of Jerusalem, Israel; Universidad de Valladolid, Valladolid, Spain)

Publisher's Version Article: stoc26main-p21-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p24-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p25-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p26-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p31-p (type: Full Paper) doi:10.1145/3798129.3800727

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

Publisher's Version Article: stoc26main-p34-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p38-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p48-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p52-p (type: Full Paper) doi:10.1145/3798129.3800731

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

Publisher's Version Article: stoc26main-p53-p (type: Full Paper) 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)

Publisher's Version Info Article: stoc26main-p55-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p56-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p65-p (type: Full Paper) doi:10.1145/3798129.3800735

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

Publisher's Version Article: stoc26main-p68-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p69-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p81-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p85-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p87-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p98-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p103-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p108-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p111-p (type: Full Paper) doi:10.1145/3798129.3800744

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

Publisher's Version Article: stoc26main-p120-p (type: Full Paper) doi:10.1145/3798129.3800745

Shortcutting for Negative-Weight Shortest Paths
George Z. Li, Jason Li, Satish Rao, and Junkai Zhang
(Carnegie Mellon University, USA; University of California at Berkeley, USA; Tsinghua University, China)

Publisher's Version Article: stoc26main-p125-p (type: Full Paper) doi:10.1145/3798129.3800746

Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
Fedor V. Fomin, Petr A. Golovach, Nikola Jedličková, Jan Kratochvíl, Danil Sagunov, and Kirill Simonov
(University of Bergen, Norway; Charles University, Czech Republic; Saint Petersburg State University, Russian Federation; V.A.Steklov Mathematical Institute of the Russian Academy of Sciences, Russian Federation)

Publisher's Version Article: stoc26main-p127-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p138-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p148-p (type: Full Paper) doi:10.1145/3798129.3800749

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

Publisher's Version Info Article: stoc26main-p157-p (type: Full Paper) doi:10.1145/3798129.3800750

MIPᶜᵒ=coRE
Junqiao (Randy) Lin
(CWI, Netherlands; QuSoft, Netherlands)

Publisher's Version Article: stoc26main-p163-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p169-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p171-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p175-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p177-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p178-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p181-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p183-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p187-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p193-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p202-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p206-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p209-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p217-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p221-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p226-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p227-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p234-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p245-p (type: Full Paper) doi:10.1145/3798129.3800769

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

Publisher's Version Article: stoc26main-p247-p (type: Full Paper) doi:10.1145/3798129.3800770

Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak
(McGill University, Canada; Ohio State University, USA)

Publisher's Version Article: stoc26main-p250-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p255-p (type: Full Paper) 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)

Publisher's Version Article: stoc26main-p264-p (type: Full Paper) 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)

Publisher's Version Published Artifact Video Info Artifacts Available Article: stoc26main-p268-p (type: Full Paper) doi:10.1145/3798129.3806376

Coq-BB5 release v1.0.0 (doi:10.5281/zenodo.17061968): Coq-BB5: Coq proof of BB(5) = 47,176,870. See GitHub repository: https://github.com/ccz181078/Coq-BB5/releases/tag/v1.0.0

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

Publisher's Version Article: stoc26main-p269-p (type: Full Paper) doi:10.1145/3798129.3800774

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

Publisher's Version Article: stoc26main-p270-p (type: Full Paper) doi:10.1145/3798129.3800775

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

Publisher's Version Article: stoc26main-p275-p (type: Full Paper) doi:10.1145/3798129.3800776

Perfect Network Resilience in Polynomial Time
Matthias Bentert and Stefan Schmid
(TU Berlin, Germany; Fraunhofer SIT, Germany)

Publisher's Version Article: stoc26main-p277-p (type: Full Paper) doi:10.1145/3798129.3800777

From Random to Explicit via Subspace Designs with Applications to Local Properties and Matroids
Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang
(University of California at Berkeley, USA; University of Michigan, USA; Massachusetts Institute of Technology, USA; Ohio State University, USA)

Publisher's Version Article: stoc26main-p281-p (type: Full Paper) doi:10.1145/3798129.3800778

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
Prateek Dwivedi, Benedikt Pago, and Tim Seppelt
(IT University of Copenhagen, Denmark; University of Cambridge, UK)

Publisher's Version Article: stoc26main-p286-p (type: Full Paper) doi:10.1145/3798129.3800779

Kolmogorov’s Approach to P vs. NP: Chain Rules for Time-Bounded Kolmogorov Complexity
Valentine Kabanets and Antonina Kolokolova
(Simon Fraser University, Canada; Memorial University of Newfoundland, Canada)

Publisher's Version Article: stoc26main-p288-p (type: Full Paper) doi:10.1145/3798129.3800780

Reviving Thorup’s Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, and Leon Schiller
(New York University, USA; Carnegie Mellon University, USA; ETH Zurich, Switzerland; INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; University of Michigan, USA; MPI-INF, Germany; Saarland University, Germany; Hasso Plattner Institute - University of Potsdam, Germany)

Publisher's Version Article: stoc26main-p292-p (type: Full Paper) doi:10.1145/3798129.3800781

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

Publisher's Version Article: stoc26main-p297-p (type: Full Paper) doi:10.1145/3798129.3800782

A Meta-complexity Characterization of Minimal Quantum Cryptography
Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li
(University of Oxford, UK; Tsinghua University, China; University of Washington, USA; EPFL, Switzerland)

Publisher's Version Info Article: stoc26main-p298-p (type: Full Paper) doi:10.1145/3798129.3800783

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

Publisher's Version Article: stoc26main-p303-p (type: Full Paper) doi:10.1145/3798129.3800784

Lower Estimates for 𝐿₁-Distortion of Transportation Cost Spaces
Chris Gartland and Mikhail Ostrovskii
(University of North Carolina at Charlotte, USA; St. John's University, USA)

Publisher's Version Article: stoc26main-p304-p (type: Full Paper) doi:10.1145/3798129.3800785

Approximating Gains-from-Trade in Matching Markets
Moshe Babaioff, Aviad Rubinstein, Xizhi Tan, and Kangning Wang
(Hebrew University of Jerusalem, Israel; Stanford University, USA; Rutgers University, USA)

Publisher's Version Article: stoc26main-p305-p (type: Full Paper) doi:10.1145/3798129.3800786

Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang
(Tel Aviv University, Israel; Google Research, Israel; Purdue University, USA; Technion, Israel)

Publisher's Version Article: stoc26main-p308-p (type: Full Paper) doi:10.1145/3798129.3800787

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

Publisher's Version Article: stoc26main-p310-p (type: Full Paper) doi:10.1145/3798129.3800788

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

Publisher's Version Article: stoc26main-p322-p (type: Full Paper) doi:10.1145/3798129.3800789

Trust Region Interior Point Methods: Optimal ℓ₂- and Faster Wide-Neighborhood Path Following
Daniel Dadush, Haoyuan Ma, Bento Natura, and László A. Végh
(CWI, Netherlands; University of Bonn, Germany; Columbia University, USA)

Publisher's Version Article: stoc26main-p331-p (type: Full Paper) doi:10.1145/3798129.3800790

High-Accuracy List-Decodable Mean Estimation
Ziyun Chen, Spencer Compton, Daniel M. Kane, and Jerry Li
(University of Washington, USA; Stanford University, USA; University of California at San Diego, USA)

Publisher's Version Article: stoc26main-p335-p (type: Full Paper) doi:10.1145/3798129.3800791

On the Informativeness of Moments in Optimal Stopping
José Correa, Andrés Cristi, Vasilis Livanos, Victor Verdugo, and Jiechen Zhang
(Universidad de Chile, Chile; EPFL, Switzerland; Center for Mathematical Modeling, Chile; Pontificia Universidad Católica de Chile, Chile)

Publisher's Version Article: stoc26main-p342-p (type: Full Paper) doi:10.1145/3798129.3800792

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
Jiawei Li, Yuhao Li, and Hanlin Ren
(University of Texas at Austin, USA; Columbia University, USA; Institute for Advanced Study at Princeton, USA)

Publisher's Version Article: stoc26main-p343-p (type: Full Paper) doi:10.1145/3798129.3800793

Testing Noisy Low-Degree Polynomials for Sparsity
Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, and Nathan White
(University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; Columbia University, USA)

Publisher's Version Article: stoc26main-p348-p (type: Full Paper) doi:10.1145/3798129.3800794

Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes
Fernando Granha Jeronimo and Nikhil Shagrithaya
(University of Illinois at Urbana-Champaign, USA; University of Michigan at Ann Arbor, USA)

Publisher's Version Article: stoc26main-p352-p (type: Full Paper) doi:10.1145/3798129.3800795

Average Hardness of SIVP for Module Lattices of Fixed Rank
Koen de Boer, Aurel Page, Radu Toma, and Benjamin Wesolowski
(Unaffiliated, Netherlands; Inria - Univ. Bordeaux - CNRS - Bordeaux INP - IMB - UMR 5251, France; Sorbonne Univ. - Univ. Paris Cité - CNRS - IMJ-PRG, France; ENS de Lyon - CNRS - UMPA - UMR 5669, France)

Publisher's Version Article: stoc26main-p353-p (type: Full Paper) doi:10.1145/3798129.3800796

Contention Resolution, with and without a Global Clock
Zixi Cai, Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie, and Ben Plosk
(Tsinghua University, China; Bar-Ilan University, Israel; University of Michigan, USA)

Publisher's Version Article: stoc26main-p360-p (type: Full Paper) doi:10.1145/3798129.3800797

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

Publisher's Version Article: stoc26main-p363-p (type: Full Paper) doi:10.1145/3798129.3800798

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

Publisher's Version Article: stoc26main-p364-p (type: Full Paper) doi:10.1145/3798129.3800799

Average-Case Complexity of Quantum Stabilizer Decoding
Andrey Boris Khesin, Jonathan Lu, Alexander Poremba, Akshar Ramkumar, and Vinod Vaikuntanathan
(University of Oxford, UK; Massachusetts Institute of Technology, USA; Boston University, USA; California Institute of Technology, USA)

Publisher's Version Article: stoc26main-p373-p (type: Full Paper) doi:10.1145/3798129.3800800

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

Publisher's Version Article: stoc26main-p379-p (type: Full Paper) doi:10.1145/3798129.3800801

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

Publisher's Version Article: stoc26main-p385-p (type: Full Paper) doi:10.1145/3798129.3800802

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

Publisher's Version Article: stoc26main-p388-p (type: Full Paper) doi:10.1145/3798129.3800803

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

Publisher's Version Article: stoc26main-p393-p (type: Full Paper) doi:10.1145/3798129.3800804

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

Publisher's Version Article: stoc26main-p395-p (type: Full Paper) doi:10.1145/3798129.3800805

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

Publisher's Version Article: stoc26main-p396-p (type: Full Paper) doi:10.1145/3798129.3800806

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

Publisher's Version Article: stoc26main-p403-p (type: Full Paper) doi:10.1145/3798129.3800807

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

Publisher's Version Article: stoc26main-p404-p (type: Full Paper) doi:10.1145/3798129.3800808

Lower Bounds for Near-Quadratic-Depth Resolution over Parities
Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, and Russell Impagliazzo
(Tata Institute of Fundamental Research, Mumbai, India; University of California at San Diego, USA)

Publisher's Version Article: stoc26main-p416-p (type: Full Paper) doi:10.1145/3798129.3800809

New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
Jin-Yi Cai, Austen Fan, Shuai Shao, and Zhuxiao Tang
(University of Wisconsin-Madison, USA; University of Science and Technology of China, China)

Publisher's Version Article: stoc26main-p428-p (type: Full Paper) doi:10.1145/3798129.3800810

Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints
Sepehr Assadi, Max Jiang, and Mars Xiang
(University of Waterloo, Canada)

Publisher's Version Article: stoc26main-p429-p (type: Full Paper) doi:10.1145/3798129.3800811

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

Publisher's Version Article: stoc26main-p435-p (type: Full Paper) doi:10.1145/3798129.3800812

Oracle Subset Problems: A Meta-algorithm for FPT Approximation via Random Walks
Ishan Chakraborty, Tanmay Inamdar, Ariel Kulik, Madhumita Kundu, and Saket Saurabh
(Institute of Mathematical Sciences, India; IIT Jodhpur, India; Ben-Gurion University of the Negev, Israel; University of Bergen, Norway)

Publisher's Version Article: stoc26main-p443-p (type: Full Paper) doi:10.1145/3798129.3800813

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
Bernhard Haeupler, Yaowei Long, Antti Roeyskoe, and Thatchaphol Saranurak
(INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; University of Michigan, USA)

Publisher's Version Article: stoc26main-p454-p (type: Full Paper) doi:10.1145/3798129.3800814

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
Sándor Kisfaludi-Bak and Dániel Marx
(Aalto University, Espoo, Finland; CISPA Helmholtz Center for Information Security, Germany)

Publisher's Version Article: stoc26main-p460-p (type: Full Paper) doi:10.1145/3798129.3800815

Breaking Barriers for Distributed MIS by Faster Degree Reduction
Seri Khoury and Aaron Schild
(INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; Google Research, USA)

Publisher's Version Article: stoc26main-p470-p (type: Full Paper) doi:10.1145/3798129.3800816

Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos
(Royal Holloway University of London, UK; University of Liverpool, UK; University of Oxford, UK; University of Essex, UK)

Publisher's Version Article: stoc26main-p474-p (type: Full Paper) doi:10.1145/3798129.3800817

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

Publisher's Version Article: stoc26main-p480-p (type: Full Paper) doi:10.1145/3798129.3800818

On the Computational Hardness of Transformers
Barna Saha, Yinzhan Xu, Christopher Ye, and Hantao Yu
(University of California at San Diego, USA; Columbia University, USA)

Publisher's Version Article: stoc26main-p482-p (type: Full Paper) doi:10.1145/3798129.3800819

Quantum Precomputation: Parallelizing Cascade Circuits and the Moore–Nilsson Conjecture Is False
Adam Bene Watts, Charles R. Chen, J. William Helton, and Joseph Slote
(University of Calgary, Canada; University of California at San Diego, USA; University of Washington, USA)

Publisher's Version Article: stoc26main-p487-p (type: Full Paper) doi:10.1145/3798129.3800820

Ideals, Macaulay Bases, and PCPs
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, and Sophus Valentin Willumsgaard
(Harvard University, USA; University of Copenhagen, Denmark)

Publisher's Version Article: stoc26main-p505-p (type: Full Paper) doi:10.1145/3798129.3800821

Memory Reallocation with Polylogarithmic Overhead
Ce Jin
(University of California at Berkeley, USA)

Publisher's Version Article: stoc26main-p510-p (type: Full Paper) doi:10.1145/3798129.3800822

Greedy Open Addressing Revisited: Beyond Yao’s Lower Bound
Martín Farach-Colton, Andrew Krapivin, and William Kuszmaul
(New York University, USA; Carnegie Mellon University, USA)

Publisher's Version Article: stoc26main-p516-p (type: Full Paper) doi:10.1145/3798129.3800823

Monotone Circuit Complexity of Matching
Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov
(University of Oxford, UK; EPFL, Switzerland; Université de Montréal, Canada)

Publisher's Version Info Article: stoc26main-p518-p (type: Full Paper) doi:10.1145/3798129.3800824

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

Publisher's Version Article: stoc26main-p521-p (type: Full Paper) doi:10.1145/3798129.3800825

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
Debajyoti Kar, Arindam Khan, and Andreas Wiese
(IISc Bengaluru, India; TU Munich, Germany)

Publisher's Version Article: stoc26main-p522-p (type: Full Paper) doi:10.1145/3798129.3800826

On Proximity Gaps of Reed-Solomon Codes
Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, and Shubhangi Saraf
(StarkWare Industries, Israel; StarkWare Industries, Poland; University of Toronto, Canada)

Publisher's Version Article: stoc26main-p523-p (type: Full Paper) doi:10.1145/3798129.3800827

Parallel Sampling via Autospeculation
Nima Anari, Carlo Baronio, CJ Chen, Alireza Haqi, Frederic Koehler, Anqi Li, and Thuy-Duong Vuong
(Stanford University, USA; University of Arizona, USA; University of Chicago, USA; University of California at San Diego, USA)

Publisher's Version Article: stoc26main-p524-p (type: Full Paper) doi:10.1145/3798129.3800828

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

Publisher's Version Article: stoc26main-p530-p (type: Full Paper) doi:10.1145/3798129.3800829

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

Publisher's Version Article: stoc26main-p535-p (type: Full Paper) doi:10.1145/3798129.3800830

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

Publisher's Version Article: stoc26main-p545-p (type: Full Paper) doi:10.1145/3798129.3800831

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time Barrier
Sayan Bhattacharya, Ermiya Farokhnejad, and Haoze Wang
(University of Warwick, UK; Peking University, China)

Publisher's Version Article: stoc26main-p548-p (type: Full Paper) doi:10.1145/3798129.3800832

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
Slobodan Mitrović, Srikkanth Ramachandran, Ronitt Rubinfeld, and Mihir Singhal
(University of California at Davis, USA; University of Novi Sad, Serbia; Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)

Publisher's Version Article: stoc26main-p551-p (type: Full Paper) doi:10.1145/3798129.3800833

Mixing of General Biased Adjacent Transposition Chains
Reza Gheissari, Holden Lee, and Eric Vigoda
(Northwestern University, USA; Johns Hopkins University, USA; University of California at Santa Barbara, USA)

Publisher's Version Article: stoc26main-p565-p (type: Full Paper) doi:10.1145/3798129.3800834

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

Publisher's Version Article: stoc26main-p569-p (type: Full Paper) doi:10.1145/3798129.3800835

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

Publisher's Version Article: stoc26main-p571-p (type: Full Paper) doi:10.1145/3798129.3800836

The Debiased Keyl’s Algorithm: A New Unbiased Estimator for Full State Tomography
Angelos Pelecanos, Jack Spilecki, and John Wright
(University of California at Berkeley, USA)

Publisher's Version Article: stoc26main-p589-p (type: Full Paper) doi:10.1145/3798129.3800837

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

Publisher's Version Article: stoc26main-p590-p (type: Full Paper) doi:10.1145/3798129.3800838

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

Publisher's Version Article: stoc26main-p594-p (type: Full Paper) doi:10.1145/3798129.3800839

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

Publisher's Version Article: stoc26main-p601-p (type: Full Paper) doi:10.1145/3798129.3800840

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

Publisher's Version Article: stoc26main-p606-p (type: Full Paper) doi:10.1145/3798129.3800841

A Theory for Probabilistic Polynomial-Time Reasoning
Lijie Chen, Jiatu Li, Igor C. Oliveira, and Ryan Williams
(University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; University of Warwick, UK)

Publisher's Version Article: stoc26main-p624-p (type: Full Paper) doi:10.1145/3798129.3800842

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

Publisher's Version Info Article: stoc26main-p628-p (type: Full Paper) doi:10.1145/3798129.3800843

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

Publisher's Version Article: stoc26main-p633-p (type: Full Paper) doi:10.1145/3798129.3800844

The Sample Complexity of Uniform Approximation for Multi-dimensional CDFs and Fixed-Price Mechanisms
Matteo Castiglioni, Anna Lunghi, and Alberto Marchesi
(Politecnico di Milano, Italy)

Publisher's Version Article: stoc26main-p634-p (type: Full Paper) doi:10.1145/3798129.3800845

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

Publisher's Version Article: stoc26main-p636-p (type: Full Paper) doi:10.1145/3798129.3800846

Approximation Does Not Help in Quantum Unitary Time-Reversal
Kean Chen, Nengkun Yu, and Zhicheng Zhang
(University of Pennsylvania, USA; Stony Brook University, USA; University of Technology Sydney, Australia)

Publisher's Version Article: stoc26main-p656-p (type: Full Paper) doi:10.1145/3798129.3800847

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

Publisher's Version Article: stoc26main-p668-p (type: Full Paper) doi:10.1145/3798129.3800848

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

Publisher's Version Article: stoc26main-p673-p (type: Full Paper) doi:10.1145/3798129.3800849

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
Elena Grigorescu, Vinayak M. Kumar, Peter Manohar, and Geoffrey Mon
(University of Waterloo, Canada; University of Texas at Austin, USA; Institute for Advanced Study at Princeton, USA)

Publisher's Version Article: stoc26main-p674-p (type: Full Paper) doi:10.1145/3798129.3800850

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
Monika Henzinger, Robin Münk, and Harald Räcke
(IST Austria, Austria; TU Munich, Germany)

Publisher's Version Article: stoc26main-p678-p (type: Full Paper) doi:10.1145/3798129.3800851

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

Publisher's Version Article: stoc26main-p703-p (type: Full Paper) doi:10.1145/3798129.3800852

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick
(University of California at Berkeley, USA; University of Michigan, USA; University of Chicago, USA; Tel Aviv University, Israel)

Publisher's Version Article: stoc26main-p713-p (type: Full Paper) doi:10.1145/3798129.3800853

Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
Bartłomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, and Mirza Redžić
(University of Wrocław, Poland; MPI-INF, Germany; KIT, Germany; University of California at Berkeley, USA; Stanford University, USA)

Publisher's Version Article: stoc26main-p715-p (type: Full Paper) doi:10.1145/3798129.3800854

Locally Computable High Independence Hashing
Yevgeniy Dodis, Shachar Lovett, and Daniel Wichs
(New York University, USA; University of California at San Diego, USA; Northeastern University, USA; NTT Research, USA)

Publisher's Version Article: stoc26main-p718-p (type: Full Paper) doi:10.1145/3798129.3800855

Approximate Orthogonal Vectors and Diameter via Regularity Lemma
Alexandr Andoni, Shunhua Jiang, and Stepan Zharkov
(Columbia University, USA; ETH Zurich, Switzerland)

Publisher's Version Article: stoc26main-p734-p (type: Full Paper) doi:10.1145/3798129.3800856

3-Query RLDCs Are Strictly Stronger Than 3-Query LDCs
Tom Gur, Dor Minzer, Guy Weissenberg, and Kai Zhe Zheng
(University of Cambridge, UK; Massachusetts Institute of Technology, USA; EPFL, Switzerland)

Publisher's Version Info Article: stoc26main-p741-p (type: Full Paper) doi:10.1145/3798129.3800857

Pattern-Sparse Tree Decompositions in H-Minor-Free Graphs
Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk
(CISPA Helmholtz Center for Information Security, Germany; University of Warsaw, Poland)

Publisher's Version Article: stoc26main-p775-p (type: Full Paper) doi:10.1145/3798129.3800858

A Dobrushin Condition for Quantum Markov Chains: Rapid Mixing and Conditional Mutual Information at High Temperature
Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang
(New York University, USA; University of California at Berkeley, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc26main-p776-p (type: Full Paper) doi:10.1145/3798129.3800859

Improved Bounds for Coin Flipping, Leader Election, and Random Selection
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Rocco A. Servedio
(Cornell University, USA; Columbia University, USA)

Publisher's Version Article: stoc26main-p777-p (type: Full Paper) doi:10.1145/3798129.3800860

Planar Length-Constrained Minimum Spanning Trees
D Ellis Hershkowitz and Richard Z Huang
(Brown University, USA)

Publisher's Version Article: stoc26main-p778-p (type: Full Paper) doi:10.1145/3798129.3800861

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

Publisher's Version Article: stoc26main-p791-p (type: Full Paper) doi:10.1145/3798129.3800862

An Optimal Algorithm for Stochastic Vertex Cover
Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Clifford Stein, Miltiadis Stouras, Ola Svensson, and Ali Vakilian
(Georgia Institute of Technology, USA; DTU, Denmark; Stanford University, USA; Duke University, USA; Columbia University, USA; EPFL, Switzerland; Virginia Tech, USA)

Publisher's Version Article: stoc26main-p798-p (type: Full Paper) doi:10.1145/3798129.3800863

Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes
Rohan Goyal and Venkatesan Guruswami
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)

Publisher's Version Article: stoc26main-p809-p (type: Full Paper) doi:10.1145/3798129.3800864

Polynomial Identity Testing and the Ideal Proof System: PIT Is in NP If and Only If IPS Can Be p-Simulated by a Cook-Reckhow Proof System
Joshua A. Grochow
(University of Colorado Boulder, USA)

Publisher's Version Article: stoc26main-p813-p (type: Full Paper) doi:10.1145/3798129.3800865

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

Publisher's Version Article: stoc26main-p827-p (type: Full Paper) doi:10.1145/3798129.3800866

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

Publisher's Version Article: stoc26main-p834-p (type: Full Paper) doi:10.1145/3798129.3800867

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

Publisher's Version Article: stoc26main-p840-p (type: Full Paper) doi:10.1145/3798129.3800868

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

Publisher's Version Article: stoc26main-p850-p (type: Full Paper) doi:10.1145/3798129.3800869

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

Publisher's Version Article: stoc26main-p851-p (type: Full Paper) doi:10.1145/3798129.3800870

Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng
(Yale University, USA; Massachusetts Institute of Technology, USA; University of Southern California, USA; University of Virginia, USA)

Publisher's Version Article: stoc26main-p859-p (type: Full Paper) doi:10.1145/3798129.3800871

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

Publisher's Version Article: stoc26main-p871-p (type: Full Paper) doi:10.1145/3798129.3800872

Non-adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-Like Inequality for Permutations
Itai Dinur, Nathan Keller, and Avichai Marmor
(Ben-Gurion University of the Negev, Israel; Georgetown University, USA; Bar-Ilan University, Israel)

Publisher's Version Article: stoc26main-p879-p (type: Full Paper) doi:10.1145/3798129.3800873

Learning Read-Once Determinants and the Principal Minor Assignment Problem
Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Chandan Saha
(IISc Bangalore, India; IIT Kharagpur, India; ISI Kolkata, India; IIT Bombay, India; Ohio State University, USA)

Publisher's Version Article: stoc26main-p909-p (type: Full Paper) doi:10.1145/3798129.3800875

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

Publisher's Version Article: stoc26main-p926-p (type: Full Paper) doi:10.1145/3798129.3800876

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

Publisher's Version Article: stoc26main-p928-p (type: Full Paper) doi:10.1145/3798129.3800877

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

Publisher's Version Article: stoc26main-p954-p (type: Full Paper) doi:10.1145/3798129.3800878

SVP_p Is Deterministically NP-Hard for All p > 2, Even to Approximate within a Factor of 2^log1-εn
Isaac M. Hair and Amit Sahai
(University of California at Santa Barbara, USA; University of California at Los Angeles, USA)

Publisher's Version Article: stoc26main-p958-p (type: Full Paper) doi:10.1145/3798129.3800879

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

Publisher's Version Article: stoc26main-p975-p (type: Full Paper) doi:10.1145/3798129.3800880

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

Publisher's Version Article: stoc26main-p984-p (type: Full Paper) doi:10.1145/3798129.3800881

Nonuniform Graph Partitioning with Just a Little Flex
Neil Olver, Harald Räcke, and Stefan Schmid
(London School of Economics and Political Science, UK; TU Munich, Germany; TU Berlin, Germany; Fraunhofer SIT, Germany)

Publisher's Version Article: stoc26main-p989-p (type: Full Paper) doi:10.1145/3798129.3800882

Rigorous Implications of the Low-Degree Heuristic
Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, and Stefan Tiegel
(Massachusetts Institute of Technology, USA; University of California at San Diego, USA; Princeton University, USA; University of Washington, USA; Northwestern University, USA)

Publisher's Version Article: stoc26main-p995-p (type: Full Paper) doi:10.1145/3798129.3800883

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

Publisher's Version Article: stoc26main-p999-p (type: Full Paper) doi:10.1145/3798129.3800884

Optimal Phylogenetic Reconstruction from Sampled Quartets
Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, and Konstantin Makarychev
(Northwestern University, USA; University of California at Santa Cruz, USA)

Publisher's Version Article: stoc26main-p1059-p (type: Full Paper) doi:10.1145/3798129.3800885

High Rate Efficient Local List Decoding from HDX
Yotam Dikstein, Max Hopkins, Toniann Pitassi, and Russell Impagliazzo
(Institute for Advanced Study at Princeton, USA; Princeton University, USA; Columbia University, USA; University of California at San Diego, USA)

Publisher's Version Article: stoc26main-p1064-p (type: Full Paper) doi:10.1145/3798129.3800886

First-Order (Coarse) Correlated Equilibria in Non-concave Games
Mete Şeref Ahunbay
(CNRS - Université Grenoble Alpes - Inria - LIG, France; TU Munich, Germany; University of Oxford, UK)

Publisher's Version Article: stoc26main-p1080-p (type: Full Paper) doi:10.1145/3798129.3800887

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

Publisher's Version Article: stoc26main-p1088-p (type: Full Paper) doi:10.1145/3798129.3800888

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)

Publisher's Version Article: stoc26main-p1095-p (type: Full Paper) doi:10.1145/3798129.3800889

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)

Publisher's Version Article: stoc26main-p1125-p (type: Full Paper) doi:10.1145/3798129.3800890

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

Publisher's Version Article: stoc26main-p1134-p (type: Full Paper) doi:10.1145/3798129.3800891

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

Publisher's Version Article: stoc26main-p1143-p (type: Full Paper) doi:10.1145/3798129.3800892

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

Publisher's Version Article: stoc26main-p1150-p (type: Full Paper) doi:10.1145/3798129.3800893

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, USA; IDSIA at USI-SUPSI, Switzerland; University of Michigan, USA; Université Paris-Cité - CNRS, France)

Publisher's Version Article: stoc26main-p1152-p (type: Full Paper) doi:10.1145/3798129.3800894

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)

Publisher's Version Article: stoc26main-p1195-p (type: Full Paper) doi:10.1145/3798129.3800895

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

Publisher's Version Article: stoc26main-p1237-p (type: Full Paper) doi:10.1145/3798129.3800896

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

Publisher's Version Article: stoc26main-p1245-p (type: Full Paper) doi:10.1145/3798129.3800897

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

Publisher's Version Article: stoc26main-p1260-p (type: Full Paper) doi:10.1145/3798129.3800898

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

Publisher's Version Article: stoc26main-p1266-p (type: Full Paper) doi:10.1145/3798129.3800899

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

Publisher's Version Article: stoc26main-p1268-p (type: Full Paper) doi:10.1145/3798129.3800900

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

Publisher's Version Article: stoc26main-p1274-p (type: Full Paper) doi:10.1145/3798129.3800901

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)

Publisher's Version Article: stoc26main-p1292-p (type: Full Paper) doi:10.1145/3798129.3800902

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)

Publisher's Version Article: stoc26main-p1321-p (type: Full Paper) doi:10.1145/3798129.3800903

Combinatorial Optimization using Comparison Oracles
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Reddy 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)

Publisher's Version Info Article: stoc26main-p1341-p (type: Full Paper) doi:10.1145/3798129.3800904

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

Publisher's Version Article: stoc26main-p1352-p (type: Full Paper) doi:10.1145/3798129.3800905

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

Publisher's Version Article: stoc26main-p1368-p (type: Full Paper) doi:10.1145/3798129.3800906

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)

Publisher's Version Article: stoc26main-p1390-p (type: Full Paper) doi:10.1145/3798129.3800907

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

Publisher's Version Article: stoc26main-p1402-p (type: Full Paper) doi:10.1145/3798129.3800908

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; City University of Hong Kong, Dongguan, China)

Publisher's Version Article: stoc26main-p1408-p (type: Full Paper) doi:10.1145/3798129.3800909

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)

Publisher's Version Article: stoc26main-p1419-p (type: Full Paper) doi:10.1145/3798129.3800910

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

Publisher's Version Article: stoc26main-p1423-p (type: Full Paper) doi:10.1145/3798129.3800911

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)

Publisher's Version Article: stoc26main-p1425-p (type: Full Paper) doi:10.1145/3798129.3800912

Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling
Karl Bringmann, Anita Dürr, and Karol Węgrzycki
(ETH Zurich, Zurich, Switzerland; MPI-INF, Germany)

Publisher's Version Article: stoc26main-p1518-p (type: Full Paper) doi:10.1145/3798129.3800913

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

Publisher's Version Article: stoc26main-p1520-p (type: Full Paper) doi:10.1145/3798129.3800914

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

Publisher's Version Article: stoc26main-p1536-p (type: Full Paper) doi:10.1145/3798129.3800915

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)

Publisher's Version Article: stoc26main-p1557-p (type: Full Paper) doi:10.1145/3798129.3800916

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)

Publisher's Version Article: stoc26main-p1565-p (type: Full Paper) doi:10.1145/3798129.3800917

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

Publisher's Version Article: stoc26main-p1663-p (type: Full Paper) doi:10.1145/3798129.3800918

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)

Publisher's Version Article: stoc26main-p1666-p (type: Full Paper) doi:10.1145/3798129.3800919

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

Publisher's Version Article: stoc26main-p1669-p (type: Full Paper) doi:10.1145/3798129.3800920

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)

Publisher's Version Article: stoc26main-p1693-p (type: Full Paper) doi:10.1145/3798129.3800921

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

Publisher's Version Article: stoc26main-p1703-p (type: Full Paper) doi:10.1145/3798129.3800922

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)

Publisher's Version Article: stoc26main-p1782-p (type: Full Paper) doi:10.1145/3798129.3800923

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

Publisher's Version Article: stoc26main-p1801-p (type: Full Paper) doi:10.1145/3798129.3800924

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

Publisher's Version Article: stoc26main-p1857-p (type: Full Paper) doi:10.1145/3798129.3800925

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)

Publisher's Version Article: stoc26main-p1875-p (type: Full Paper) doi:10.1145/3798129.3800926

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

Publisher's Version Article: stoc26main-p1957-p (type: Full Paper) doi:10.1145/3798129.3800927

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)

Publisher's Version Article: stoc26main-p1972-p (type: Full Paper) doi:10.1145/3798129.3800928

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)

Publisher's Version Article: stoc26main-p2045-p (type: Full Paper) doi:10.1145/3798129.3800929

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

Publisher's Version Article: stoc26main-p2089-p (type: Full Paper) doi:10.1145/3798129.3800930

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)

Publisher's Version Article: stoc26main-p2157-p (type: Full Paper) doi:10.1145/3798129.3800931