STOC 2026 Accepted Papers

---

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

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
Jason Li (CMU)

Forbidden Subgraphs of Graphs with Low Bandwidth
Maria Chudnovsky (Princeton University, USA); Daniel Lokshtanov (University of California Santa Barbara, USA); Eran Nevo (Hebrew University, Israel)

SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to use the simplicity of cryptographic reasoning)
Yao-Ching Hsieh (University of Washington); Abhishek Jain (NTT Research and John Hopkins); Jiatu Li (MIT); Surya Mathialagan (NTT Research)

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

Few Single-Qubit Measurements Suffice to Certify Any Quantum State
Meghal Gupta (UC Berkeley); William He, Ryan O'Donnell (Carnegie Mellon University)

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

Near Optimal Hardness of Approximating k-CSP
Dor Minzer, Kai Zhe Zheng (MIT)

On the Learning Curves of Revenue Maximization
Steve Hanneke (Purdue University); Alkis Kalavasis (Yale University); Shay Moran (Technion); Grigoris Velegkas (Google Research)

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

No exponential quantum speedup for SIS∞ anymore
Robin Kothari (Google Quantum AI); Ryan O'Donnell (Carnegie Mellon University); Kewen Wu (Institute for Advanced Study)

Almost-Optimal Approximation Algorithm for Global Minimum Cut in Directed Graphs
Ron Mosenzon (TTIC)

Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method
Yang Liu (Carnegie Mellon University)

S-unit equations in modules and linear-exponential Diophantine equations
Ruiwen Dong (University of Oxford); Doron Shafrir (Ben-Gurion University of the Negev)

The Weak Rank Principle: Lower Bounds and Applications
Michal Garlík, Svyatoslav Gryaznov (Imperial College London); Hanlin Ren (IAS, Princeton); Iddo Tzameret (Imperial College London)

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

Optimal Contest beyond Convexity
Negin Golrezaei (MIT); MohammadTaghi Hajiaghayi, Suho Shin (University of Maryland)

Closure under factorization from a result of Furstenberg
Somnath Bhattacharjee (University of Toronto); Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi (Tata Institute of Fundamental Research, Mumbai); Shubhangi Saraf (University of Toronto)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
Sumegha Garg (Rutgers University); Jabari Hastings, Chirag Pabbaraju (Stanford University); Vatsal Sharan (USC)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
Bernhard Haeupler (INSAIT, Sofia University "St. Kliment Ohridski" & ETH Zurich); Yonggang Jiang (Max Planck Institute for Informatics and Saarland University); Thatchaphol Saranurak (University of Michigan)

Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
Andrej Bogdanov (University of Ottawa); Alon Rosen (Bocconi University); Neekon Vafa, Vinod Vaikuntanathan (MIT)

Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Eleon Bach (TU Munich); Alexander E. Black (Bowdoin College); Sophie Huiberts (LIMOS, CNRS, University Clermont Auvergne); Sean Kafer (Illinois State University)

Sampling Permutations with Cell Probes is Hard
Yaroslav Alekseev (Technion); Mika Göös, Konstantin Myasnikov, Artur Riazanov (EPFL); Dmitry Sokolov (EPFL, Universite de Montreal)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
Yumou Fei, Dor Minzer, Shuo Wang (MIT)

NP-membership for the boundary-boundary art-gallery problem
Jack Stade (University of Copenhagen)

Shortcutting for Negative-Weight Shortest Paths
George Z. Li, Jason Li (CMU); Satish Rao (UC Berkeley); Junkai Zhang (Tsinghua University)

Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
Fedor V. Fomin, Petr A. Golovach (University of Bergen); Nikola Jedličková (Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University); Jan Kratochvíl (Charles University); Danil Sagunov (ITMO University); Kirill Simonov (University of Bergen)

Fisher Meets Lindahl: A Unified Duality Framework for Market Equilibrium
Yixin Tao (Shanghai University of Finance and Economics); Weiqiang Zheng (Yale University)

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
Amey Bhangale (UC Riverside); Mark Braverman (Princeton University); Subhash Khot (New York University); Yang Liu (Carnegie Mellon University); Dor Minzer (MIT); Kunal Mittal (New York University)

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

MIPco=coRE
Junqiao (Randy) Lin (CWI & Qusoft)

The Skolem Problem in rings of positive characteristic
Ruiwen Dong (University of Oxford); Doron Shafrir (Ben-Gurion University of the Negev)

Fine-Grained Complexity of Continuous Euclidean k-Center
Lotte Blank (University of Bonn); Karl Bringmann (Saarland University and Max-Planck-Institute for Informatics); Parinya Chalermsook (University of Sheffield); Karthik C. S. (Rutgers University); Benedikt Kolbe (Hausdorff Center for Mathematics, University of Bonn); Hung Le (University of Massachusetts, Amherst, USA); Geert van Wordragen (Aalto University)

Generalized Samorodnitsky noisy function inequalities, with applications to error-correcting codes
Olakunle Sunday Abawonse, Jan Hązła (AIMS Rwanda); Ryan O'Donnell (Carnegie Mellon University)

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

Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb Inequalities
Joshua Brakensiek (University of California, Berkeley); Yeyuan Chen (University of Michigan); Manik Dhar (MIT); Zihan Zhang (The Ohio State University)

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

Tâtonnement Dynamics for Fisher Markets with Chores
Bhaskar Ray Chaudhury (University of Illinois at Urbana-Champaign); Christian Kroer (Columbia University); Ruta Mehta (University of Illinois at Urbana-Champaign); Tianlong Nan (Columbia University)

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

Hesse’s Redemption: Efficient Convex Polynomial Programming
Lucas Slot, David Steurer, Manuel Wiedmer (ETH Zürich)

Sparsifying Suprema of Gaussian Processes
Anindya De (University of Pennsylvania); Shivam Nadimpalli (MIT); Ryan O'Donnell (CMU); Rocco A. Servedio (Columbia University)

Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
Nikhil Bansal (University of Michigan); Haotian Jiang (University of Chicago)

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

On the Cryptographic Foundations of Interactive Quantum Advantage
Kabir Tomer (University of Illinois Urbana-Champaign); Mark Zhandry (Stanford University & NTT Research)

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

Learning CNF formulas from uniform random solutions in the local lemma regime
Weiming Feng (The University of Hong Kong); Xiongxin Yang (University of California, Santa Barbara); Yixiao Yu, Yiyao Zhang (Nanjing University)

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

Better neural network expressivity: subdividing the simplex
Egor Bakaev, Florestan Brunck (University of Copenhagen); Christoph Hertrich (University of Technology Nuremberg); Jack Stade (University of Copenhagen); Amir Yehudayoff (University of Copenhagen, Technion-IIT)

On Zeros and Algorithms for Disordered Systems: Mean-Field Spin Glasses
Ferenc Bencs (Centrum Wiskunde & Informatica); Brice Huang (Stanford University); Daniel Z. Lee, Kuikui Liu (MIT); Guus Regts (University of Amsterdam)

Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time
Mehrdad Ghadiri (MIT); Junzhao Yang (Carnegie Mellon University); Angelo Farfan (MIT)

Borsuk-Ulam and replicable learning of large-margin halfspaces
Ari Blondal, Hamed Hatami (McGill University); Pooya Hatami, Chavdar Lalov, Sivan Tretiak (The Ohio State University)

Efficient Quantum Hermite Transform
Siddhartha Jain (University of Texas at Austin, Google); Vishnu Iyer (University of Texas at Austin); Rolando D. Somma (Google); Ning Bao (Northeastern, Brookhaven National Lab); Stephen Jordan (Google)

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

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

Dynamic Meta-Kernelization
Christian Bertram (University of Copenhagen); Deborah Haun (Karlsruhe Institute of Technology); Mads Vestergaard Jensen, Tuukka Korhonen (University of Copenhagen)

Boolean function monotonicity testing requires (almost) n^1/2 queries
Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell (Columbia University)

Separating QMA from QCMA with a classical oracle
John Bostanci (Columbia University); Jonas Haferkamp (Saarland University); Chinmay Nirkhe (University of Washington); Mark Zhandry (NTT Research & Stanford University)

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

From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids
Joshua Brakensiek (University of California, Berkeley); Yeyuan Chen (University of Michigan); Manik Dhar (MIT); Zihan Zhang (The Ohio State University)

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

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

Reviving Thorup's Shortcut Conjecture
Aaron Bernstein (New York University); Henry Fleischmann (Carnegie Mellon University); Maximilian Probst Gutenberg (ETH Zürich); Bernhard Haeupler (INSAIT, Sofia University "St. Kliment Ohridski" & ETH Zurich); Gary Hoppenworth (University of Michigan); Yonggang Jiang (Max Planck Institute for Informatics and Saarland University); George Z. Li (Carnegie Mellon University); Seth Pettie, Thatchaphol Saranurak (University of Michigan); Leon Schiller (Hasso Plattner Institute, University of Potsdam)

SNARGs for NP and Non-Signaling PCPs, Revisited
Lalita Devadas, Sam Hopkins, Yael Kalai (MIT); Pravesh K Kothari, Alex Lombardi (Princeton); Surya Mathialagan (NTT Research)

A Meta-Complexity Characterization of Minimal Quantum Cryptography
Bruno Cavalar (University of Oxford); Boyang Chen (Tsinghua University); Andrea Coladangelo (Univerity of Washington); Matthew Gray (University of Oxford); Zihan Hu (EPFL); Zhengfeng Ji, Xingjian Li (Tsinghua University)

Fast and Compact Random Mappings with Uniform Guarantees and Applications
Ying Feng, Piotr Indyk (MIT)

Lower Estimates for L1-Distortion of Transportation Cost Spaces
Chris Gartland (UNC Charlotte); Mikhail Ostrovskii (St. John's University)

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

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

Quantum circuit lower bounds in the magic hierarchy
Natalie Parham (Columbia University)

Approximation schemes for Edit Distance and LCS in quasi-strongly subquadratic time
Xiao Mao, Aviad Rubinstein (Stanford University)

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

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

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

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

Testing noisy low-degree polynomials for sparsity
Yiqiao Bao, Anindya De (University of Pennsylvania); Shivam Nadimpalli (MIT); Rocco A. Servedio (Columbia University); Nathan White (University of Pennsylvania)

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

Average hardness of SIVP for module lattices of fixed rank
Koen de Boer (unaffiliated); Aurel Page (Inria, Univ. Bordeaux, CNRS); Radu Toma (Sorbonne Univ. and Univ. Paris Cité, CNRS); Benjamin Wesolowski (ENS de Lyon, CNRS)

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

Fast Mixing of Quantum Spin Chains at All Temperatures
Thiago Bergamaschi, Chi-Fang Chen (UC Berkeley)

Magic and communication complexity
Uma Girish (Columbia University); Alex May (Perimeter Institute for Theoretical Physics); Natalie Parham, Henry Yuen (Columbia University)

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

Clifford testing: algorithms and lower bounds
Marcel Hinsche (FU Berlin); Zongbo Bao, Phillipe van Dordrecht (CWI & QuSoft); Jens Eisert (FU Berlin); Jop Briet, Jonas Helsen (CWI & QuSoft)

Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits
Lijie Chen, Avishay Tal, Yichuan Wang (UC Berkeley)

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

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

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

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
Nick Fischer (Max Planck Institute for Informatics)

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

Steiner Forest: A Simplified Better-Than-2 Approximation
Anupam Gupta (New York University); Vera Traub (ETH Zürich)

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

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

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

Zero-free regions and concentration inequalities for hypergraph colorings in the local lemma regime
Jingcheng Liu, Yixiao Yu (Nanjing University)

Oracle Subset Problems: A Meta-Algorithm for FPT Approximation via Random Walks
Ishan Chakraborty (Institute of Mathematical Sciences, Chennai); Tanmay Inamdar (Indian Institute of Technology Jodhpur); Ariel Kulik (Ben-Gurion University); Madhumita Kundu (University of Bergen); Saket Saurabh (Institute of Mathematical Sciences)

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

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

Breaking Barriers for Distributed MIS by Faster Degree Reduction
Seri Khoury (INSAIT); Aaron Schild (Google Research)

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

Space-Efficient Dictionary Matching with Mismatches Using Function Inversion
Jackson Bibbens (UMass Amherst); Levi Borevitz (Northwestern); Samuel McCauley (Williams College)

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

Quantum precomputation: parallelizing cascade circuits and the Moore-Nilsson conjecture is false
Adam Bene Watts (University of Calgary); Charles R. Chen, J. William Helton (University of California, San Diego); Joseph Slote (University of Washington)

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

Memory Reallocation with Polylogarithmic Overhead
Ce Jin (UC Berkeley)

Greedy Open Addressing Revisited: Beyond Yao's Lower Bound
Martin Farach-Colton (New York University); Andrew Krapivin, William Kuszmaul (Carnegie Mellon University)

Monotone Circuit Complexity of Matching
Bruno Cavalar (University of Oxford); Mika Göös, Artur Riazanov, Anastasia Sofronova (EPFL); Dmitry Sokolov (EPFL, University of Montreal)

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

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
Debajyoti Kar, Arindam Khan (Indian Institute of Science, Bengaluru); Andreas Wiese (Technical University of Munich, Germany)

On proximity gaps of Reed-Solomon codes
Eli Ben-Sasson (StarkWare Industries Ltd.); Dan Carmon (StarkWare Industries Ltd); Ulrich Haböck (StarkWare Industries Ltd.); Swastik Kopparty, Shubhangi Saraf (University of Toronto)

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

Efficient reversal of transductions of sparse graph classes
Jakub Gajarský (University of Warsaw); Michał Pilipczuk (University of Warsaw, Poland); Jan Dreier (TU Wien)

Markov Chains Approximate Message Passing
Amit Rajaraman (MIT); David X Wu (UC Berkeley)

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

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

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
Slobodan Mitrović (UC Davis and University of Novi Sad); Srikkanth Ramachandran (University of California Davis); Ronitt Rubinfeld (MIT); Mihir Singhal (UC Berkeley)

Mixing of general biased adjacent transposition chains
Reza Gheissari (Northwestern University); Holden Lee (Johns Hopkins University); Eric Vigoda (University of California, Santa Barbara)

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

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

The debiased Keyl's algorithm: a new unbiased estimator for full state tomography
Angelos Pelecanos, Jack Spilecki, John Wright (UC Berkeley)

Hardness Amplification Beyond Boolean Functions
Nobutaka Shimizu, Kenji Yasunaga (Institute of Science Tokyo)

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

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

Beating Meet-in-the-Middle for Subset Balancing Problems
Tim Randolph (Harvey Mudd College); Karol Wegrzycki (Max-Planck-Institute for Informatics)

A Theory for Probabilistic Polynomial-Time Reasoning
Lijie Chen (UC Berkeley); Jiatu Li (MIT); Igor C. Oliveira (University of Warwick); Ryan Williams (MIT)

The natural proofs barrier against data-structure lower-bounds
Bruno Loff (FCUL and LASIGE, University of Lisbon); Michal Koucký (Computer Science Institute of Charles University, Prague); Tulasimohan Molli (LASIGE, University of Lisbon); Michael Saks

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

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

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

Approximation does not help in quantum unitary time-reversal
Kean Chen (University of Pennsylvania); Nengkun Yu (Stony Brook University); Zhicheng Zhang (University of Technology Sydney)

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

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

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

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

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

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

Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
Bartłomiej Dudek (University of Wrocław); Nick Fischer (Max Planck Institute for Informatics); Geri Gokaj (Karlsruhe Institute of Technology); Ce Jin (UC Berkeley); Marvin Künnemann (Karlsruhe Institute of Technology); Xiao Mao (Stanford University); Mirza Redžić (Karlsruhe Institute of Technology)

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

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

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
Tom Gur (University of Cambridge); Dor Minzer (MIT); Guy Weissenberg (EPFL); Kai Zhe Zheng (MIT)

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

A Dobrushin condition for quantum Markov chains: Rapid mixing and conditional mutual information at high temperature
Ainesh Bakshi (NYU); Allen Liu (UC Berkeley); Ankur Moitra (MIT); Ewin Tang (UC Berkeley)

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

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

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

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

Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes
Rohan Goyal (MIT); Venkatesan Guruswami (UC Berkeley)

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)

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

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

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

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
Sitan Chen (Harvard University); Jingqiu Ding (ETH Zürich); Mahbod Majid (MIT); Walt McKelvie (Harvard University)

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

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

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

Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations
Itai Dinur (Ben-Gurion University and Georgetown University); Nathan Keller (Bar Ilan University); Avichai Marmor (Bar-Ilan University)

Reach Unambiguous Logspace is almost in Logspace
V. Arvind (Institute of Mathematical Sciences (HBNI), Chennai); Samir Datta (Chennai Mathematical Institute)

Learning Read-Once Determinants and the Principal Minor Assignment Problem
Abhiram Aravind (IISc Banglore); Abhranil Chatterjee (IIT Kanpur); Sumanta Ghosh (ISI Kolkata); Rohit Gurjar (IIT Bombay); Roshan Raj (TIFR Mumbai); Chandan Saha (IISc Bangalore)

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

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
Yury Makarychev (TTIC)

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

SVP_p is NP-Hard for all p > 2, Even to Approximate Within a Factor of 2^log1-εn
Isaac M Hair (UCSB, UCLA); Amit Sahai (UCLA)

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

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

Nonuniform graph partitioning with just a little flex
Neil Olver (London School of Economics and Political Science); Harald Räcke (TU Munich); Stefan Schmid (TU Berlin and Fraunhofer SIT)

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

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 (University of Washington); Ellen Wu (Massachusetts Institute of Technology)

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

High Rate Efficient Local List Decoding from HDX
Yotam Dikstein (IAS); Max Hopkins (Princeton University); Toniann Pitassi (Columbia University); Russell Impagliazzo (University of California, San Diego)

First-order (coarse) correlated equilibria in non-concave games
Mete Şeref Ahunbay (CNRS, Université Grenoble Alpes, INRIA, LIG)

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

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

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

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

Randomized Rounding over Dynamic Programs
Etienne Bamas (EPFL); Shi Li (Nanjing University); Lars Rohwedder (University of Southern Denmark)

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

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

Restriction Trees for Sparsity and Applications
Arkadev Chattopadhyay, Yogesh Dahiya (TIFR, Mumbai); Shachar Lovett (UC San Diego)

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

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

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

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

Learning stabilizer structure of quantum states
Srinivasan Arunachalam, Arkopal Dutt (IBM Research)

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

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

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

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

Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise
Debsurya De, Dmitriy Kunisky (Johns Hopkins University)

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

Pseudodeterministic Communication Complexity
Mika Göös (EPFL); Nathaniel Harms (University of British Columbia); Artur Riazanov, Anastasia Sofronova (EPFL); Dmitry Sokolov (EPFL, University of Montreal); Weiqiang Yuan (EPFL)

Deterministic list decoding of Reed-Solomon codes
Soham Chatterjee, Mrinal Kumar, Prahladh Harsha (Tata Institute of Fundamental Research)

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

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

Negations are powerful even in small depth
Bruno Cavalar (University of Oxford); Théo Fabris (University of Copenhagen); Partha Mukhopadhyay (Chennai Mathematical Institute); Srikanth Srinivasan, Amir Yehudayoff (University of Copenhagen)

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
Alexander Armbruster (Technical University of Munich); Fabrizio Grandoni, Antoine Tinguely (IDSIA, USI-SUPSI); Andreas Wiese (Technical University of Munich)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
Karl Bringmann (Saarland University and Max-Planck-Institute for Informatics); Anita Durr (Saarland University and Max Planck Institute for Informatics); Karol Wegrzycki (Max-Planck-Institute for Informatics)

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

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

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

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

A Poisson Process for Submodular Maximization
Amit Ganz (Technion); Ariel Kulik (Ben-Gurion University); Roy Schwartz (Technion); Mohit Singh (Georgia Tech)

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

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

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

Towards Parity Not in QAC⁰
Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, John Wright (UC Berkeley)

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

Private Learning of Littlestone Classes, Revisited
Xin Lyu (UC Berkeley)

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

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

Fine-Grained Bounds for Courcelle's Theorem
Daniel Lokshtanov (University of California Santa Barbara, USA); Fahad Panolan (School of Computer Science, University of Leeds); Saket Saurabh (Institute of Mathematical Sciences); Jie Xue (New York University Shanghai); Meirav Zehavi (Ben-Gurion University)

DAG Projections: Reducing Distance and Flow Problems to DAGs
Bernhard Haeupler (INSAIT, Sofia University "St. Kliment Ohridski" & ETH Zurich); Yonggang Jiang (Max Planck Institute for Informatics and Saarland University); Thatchaphol Saranurak (University of Michigan)

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

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

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