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

Title Page

Article: stoc26foreword-fm000-p

Welcome from the Chairs

Article: stoc26foreword-fm001-p

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

Article Search Article: stoc26main-p4-p

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

Article Search Article: stoc26main-p8-p

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

Article Search Article: stoc26main-p21-p

SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to Use the Simplicity of Cryptographic Reasoning)
Yao-Ching Hsieh, Abhishek Jain, Jiatu Li, and Surya Mathialagan
(University of Washington, USA; NTT Research, USA; Johns Hopkins University, USA; Massachusetts Institute of Technology, USA)

Article Search Article: stoc26main-p24-p

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

Article Search Article: stoc26main-p25-p

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

Article Search Article: stoc26main-p26-p

Separator Theorem for Minor-Free Graphs in Linear Time
Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, and Tomáš Masařík
(CNRS - 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)

Preprint Article: stoc26main-p31-p

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

Article Search Article: stoc26main-p34-p

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

Article Search Article: stoc26main-p38-p

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

Article Search Article: stoc26main-p48-p

No Exponential Quantum Speedup for SIS∞ Anymore
Robin Kothari, Ryan O'Donnell, and Kewen Wu
(Google Quantum AI, USA; Carnegie Mellon University, USA; Institute for Advanced Study at Princeton, USA)

Article Search Article: stoc26main-p52-p

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

Preprint Article: stoc26main-p53-p

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

Preprint Info Article: stoc26main-p55-p

S-Unit Equations in Modules and Linear-Exponential Diophantine Equations
Ruiwen Dong and Doron Shafrir
(University of Oxford, UK; Ben-Gurion University of the Negev, Israel)

Article Search Article: stoc26main-p56-p

The Weak Rank Principle: Lower Bounds and Applications
Michal Garlík, Svyatoslav Gryaznov, Hanlin Ren, and Iddo Tzameret
(Imperial College London, UK; Institute for Advanced Study at Princeton, USA)

Article Search Article: stoc26main-p65-p

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

Article Search Article: stoc26main-p68-p

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

Article Search Article: stoc26main-p69-p

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

Article Search Article: stoc26main-p81-p

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

Article Search Article: stoc26main-p85-p

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
Bernhard Haeupler, Yonggang Jiang, and Thatchaphol Saranurak
(INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; MPI-INF, Germany; Saarland University, Germany; University of Michigan, USA)

Article Search Article: stoc26main-p87-p

Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
Andrej Bogdanov, Alon Rosen, Neekon Vafa, and Vinod Vaikuntanathan
(University of Ottawa, Canada; Bocconi University, Italy; Massachusetts Institute of Technology, USA)

Article Search Article: stoc26main-p98-p

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

Article Search Article: stoc26main-p103-p

Sampling Permutations with Cell Probes Is Hard
Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, and Dmitry Sokolov
(Technion, Israel; EPFL, Switzerland; Université de Montréal, Canada)

Article Search Article: stoc26main-p108-p

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

Article Search Article: stoc26main-p111-p

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

Article Search Article: stoc26main-p120-p

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

Article Search Article: stoc26main-p125-p

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

Article Search Article: stoc26main-p127-p

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

Preprint Article: stoc26main-p138-p

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
Amey Bhangale, Mark Braverman, Subhash Khot, Yang Liu, Dor Minzer, and Kunal Mittal
(University of California at Riverside, USA; Princeton University, USA; New York University, USA; Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA)

Preprint Article: stoc26main-p148-p

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

Article Search Info Article: stoc26main-p157-p

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

Preprint Article: stoc26main-p163-p

The Skolem Problem in Rings of Positive Characteristic
Ruiwen Dong and Doron Shafrir
(University of Oxford, UK; Ben-Gurion University of the Negev, Israel)

Article Search Article: stoc26main-p169-p

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)

Article Search Article: stoc26main-p171-p

Generalized Samorodnitsky Noisy Function Inequalities, with Applications to Error-Correcting Codes
Olakunle Sunday Abawonse, Jan Hązła, and Ryan O'Donnell
(AIMS, Rwanda; Carnegie Mellon University, USA)

Article Search Article: stoc26main-p175-p

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

Article Search Article: stoc26main-p177-p

Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb Inequalities
Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang
(University of California at Berkeley, USA; University of Michigan, USA; Massachusetts Institute of Technology, USA; Ohio State University, USA)

Article Search Article: stoc26main-p178-p

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

Article Search Article: stoc26main-p181-p

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

Preprint Article: stoc26main-p183-p

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

Article Search Article: stoc26main-p187-p

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

Article Search Article: stoc26main-p193-p

Sparsifying Suprema of Gaussian Processes
Anindya De, Shivam Nadimpalli, Ryan O'Donnell, and Rocco A. Servedio
(University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Columbia University, USA)

Article Search Article: stoc26main-p202-p

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

Article Search Article: stoc26main-p206-p

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

Article Search Article: stoc26main-p209-p

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

Article Search Article: stoc26main-p217-p

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

Article Search Article: stoc26main-p221-p

Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime
Weiming Feng, Xiongxin Yang, Yixiao Yu, and Yiyao Zhang
(University of Hong Kong, Hong Kong; University of California at Santa Barbara, USA; Nanjing University, China)

Article Search Article: stoc26main-p226-p

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

Article Search Article: stoc26main-p227-p

Better Neural Network Expressivity: Subdividing the Simplex
Egor Bakaev, Florestan Brunck, Christoph Hertrich, Jack Stade, and Amir Yehudayoff
(University of Copenhagen, Denmark; University of Technology Nuremberg, Germany; Technion, Israel)

Article Search Article: stoc26main-p234-p

On Zeros and Algorithms for Disordered Systems: Mean-Field Spin Glasses
Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, and Guus Regts
(CWI, Netherlands; Stanford University, USA; Massachusetts Institute of Technology, USA; University of Amsterdam, Netherlands)

Article Search Article: stoc26main-p245-p

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

Preprint Article: stoc26main-p247-p

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

Article Search Article: stoc26main-p250-p

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

Article Search Article: stoc26main-p255-p

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

Article Search Article: stoc26main-p264-p

Determination of the Fifth Busy Beaver Value
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)

Preprint Video Info Artifacts Available Article: stoc26main-p268-p

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

Preprint Article: stoc26main-p269-p

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

Article Search Article: stoc26main-p270-p

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

Preprint Article: stoc26main-p275-p

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

Article Search Article: stoc26main-p277-p

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

Article Search Article: stoc26main-p281-p

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

Preprint Article: stoc26main-p286-p

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

Article Search Article: stoc26main-p288-p

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

Preprint Article: stoc26main-p292-p

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)

Article Search Article: stoc26main-p297-p

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

Article Search Info Article: stoc26main-p298-p

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

Article Search Article: stoc26main-p303-p

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

Article Search Article: stoc26main-p304-p

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

Article Search Article: stoc26main-p305-p

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

Preprint Article: stoc26main-p308-p

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

Preprint Article: stoc26main-p310-p

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

Article Search Article: stoc26main-p322-p

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

Article Search Article: stoc26main-p331-p

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

Article Search Article: stoc26main-p335-p

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

Article Search Article: stoc26main-p342-p

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

Article Search Article: stoc26main-p343-p

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

Article Search Article: stoc26main-p348-p

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

Article Search Article: stoc26main-p352-p

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

Article Search Article: stoc26main-p353-p

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

Article Search Article: stoc26main-p360-p

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

Article Search Article: stoc26main-p363-p

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

Preprint Article: stoc26main-p364-p

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

Preprint Article: stoc26main-p373-p

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)

Article Search Article: stoc26main-p379-p

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

Article Search Article: stoc26main-p385-p

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

Article Search Article: stoc26main-p388-p

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

Article Search Article: stoc26main-p393-p

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

Preprint Article: stoc26main-p395-p

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

Article Search Article: stoc26main-p396-p

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

Article Search Article: stoc26main-p403-p

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

Article Search Article: stoc26main-p404-p

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

Article Search Article: stoc26main-p416-p

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

Article Search Article: stoc26main-p428-p

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

Article Search Article: stoc26main-p429-p

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

Article Search Article: stoc26main-p435-p

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

Article Search Article: stoc26main-p443-p

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

Article Search Article: stoc26main-p454-p

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

Preprint Article: stoc26main-p460-p

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

Preprint Article: stoc26main-p470-p

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

Article Search Article: stoc26main-p474-p

Space-Efficient 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)

Article Search Article: stoc26main-p480-p

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

Article Search Article: stoc26main-p482-p

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

Article Search Article: stoc26main-p487-p

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

Preprint Article: stoc26main-p505-p

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

Preprint Article: stoc26main-p510-p

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

Article Search Article: stoc26main-p516-p

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

Article Search Info Article: stoc26main-p518-p

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

Article Search Article: stoc26main-p521-p

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

Article Search Article: stoc26main-p522-p

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

Article Search Article: stoc26main-p523-p

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

Preprint Article: stoc26main-p524-p

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)

Article Search Article: stoc26main-p530-p

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

Article Search Article: stoc26main-p535-p

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

Article Search Article: stoc26main-p545-p

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

Preprint Article: stoc26main-p548-p

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

Preprint Article: stoc26main-p551-p

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

Article Search Article: stoc26main-p565-p

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

Article Search Article: stoc26main-p569-p

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

Preprint Article: stoc26main-p571-p

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

Article Search Article: stoc26main-p589-p

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

Article Search Article: stoc26main-p590-p

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

Article Search Article: stoc26main-p594-p

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

Article Search Article: stoc26main-p601-p

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

Article Search Article: stoc26main-p606-p

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

Article Search Article: stoc26main-p624-p

The Natural Proofs Barrier against Data-Structure Lower-Bounds
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)

Article Search Info Article: stoc26main-p628-p

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

Article Search Article: stoc26main-p633-p

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

Article Search Article: stoc26main-p634-p

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

Article Search Article: stoc26main-p636-p

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

Article Search Article: stoc26main-p656-p

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

Article Search Article: stoc26main-p668-p

What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing
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)

Article Search Article: stoc26main-p673-p

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

Preprint Article: stoc26main-p674-p

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

Preprint Article: stoc26main-p678-p

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)

Article Search Article: stoc26main-p703-p

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

Article Search Article: stoc26main-p713-p

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

Article Search Article: stoc26main-p715-p

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

Article Search Article: stoc26main-p718-p

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

Article Search Article: stoc26main-p734-p

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

Article Search Info Article: stoc26main-p741-p

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

Article Search Article: stoc26main-p775-p

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

Article Search Article: stoc26main-p776-p

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

Article Search Article: stoc26main-p777-p

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

Article Search Article: stoc26main-p778-p

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

Article Search Article: stoc26main-p791-p

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

Article Search Article: stoc26main-p798-p

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

Article Search Article: stoc26main-p809-p

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

Preprint Article: stoc26main-p813-p

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

Article Search Article: stoc26main-p827-p

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

Article Search Article: stoc26main-p834-p

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

Article Search Article: stoc26main-p840-p

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)

Preprint Article: stoc26main-p850-p

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

Article Search Article: stoc26main-p851-p

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

Preprint Article: stoc26main-p859-p

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

Article Search Article: stoc26main-p871-p

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

Article Search Article: stoc26main-p879-p

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)

Article Search Article: stoc26main-p909-p

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

Article Search Article: stoc26main-p926-p

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

Article Search Article: stoc26main-p928-p

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

Article Search Article: stoc26main-p954-p

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

Article Search Article: stoc26main-p958-p

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

Article Search Article: stoc26main-p975-p

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

Preprint Article: stoc26main-p984-p

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

Preprint Article: stoc26main-p989-p

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

Article Search Article: stoc26main-p995-p

The Power of Two Bases: 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)

Article Search Article: stoc26main-p999-p

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

Article Search Article: stoc26main-p1059-p

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

Preprint Article: stoc26main-p1064-p

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)

Article Search Article: stoc26main-p1080-p

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

Article Search Article: stoc26main-p1088-p

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

Article Search Article: stoc26main-p1095-p

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

Article Search Article: stoc26main-p1125-p

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

Article Search Article: stoc26main-p1134-p

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

Article Search Article: stoc26main-p1143-p

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

Article Search Article: stoc26main-p1150-p

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

Article Search Article: stoc26main-p1152-p

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

Preprint Article: stoc26main-p1195-p

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)

Article Search Article: stoc26main-p1237-p

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

Article Search Article: stoc26main-p1245-p

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

Article Search Article: stoc26main-p1260-p

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

Article Search Article: stoc26main-p1266-p

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

Article Search Article: stoc26main-p1268-p

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

Article Search Article: stoc26main-p1274-p

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

Article Search Article: stoc26main-p1292-p

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

Article Search Article: stoc26main-p1321-p

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

Article Search Info Article: stoc26main-p1341-p

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

Preprint Article: stoc26main-p1352-p

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

Article Search Article: stoc26main-p1368-p

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

Article Search Article: stoc26main-p1390-p

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

Article Search Article: stoc26main-p1402-p

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

Preprint Article: stoc26main-p1408-p

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

Article Search Article: stoc26main-p1419-p

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

Article Search Article: stoc26main-p1423-p

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

Article Search Article: stoc26main-p1425-p

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

Article Search Article: stoc26main-p1518-p

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

Article Search Article: stoc26main-p1520-p

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

Article Search Article: stoc26main-p1536-p

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

Article Search Article: stoc26main-p1557-p

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

Article Search Article: stoc26main-p1565-p

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

Article Search Article: stoc26main-p1663-p

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

Article Search Article: stoc26main-p1666-p

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

Article Search Article: stoc26main-p1669-p

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

Preprint Article: stoc26main-p1693-p

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

Article Search Article: stoc26main-p1703-p

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

Preprint Article: stoc26main-p1782-p

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

Article Search Article: stoc26main-p1801-p

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

Article Search Article: stoc26main-p1857-p

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

Article Search Article: stoc26main-p1875-p

Fine-Grained Bounds for Courcelle’s Theorem
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi
(University of California 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)

Article Search Article: stoc26main-p1957-p

DAG Projections: Reducing Distance and Flow Problems to DAGs
Bernhard Haeupler, Yonggang Jiang, and Thatchaphol Saranurak
(INSAIT at Sofia University St. Kliment Ohridski, Bulgaria; ETH Zurich, Switzerland; MPI-INF, Germany; Saarland University, Germany; University of Michigan, USA)

Article Search Article: stoc26main-p1972-p

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

Article Search Article: stoc26main-p2045-p

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

Article Search Article: stoc26main-p2089-p

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

Article Search Article: stoc26main-p2157-p