STOC 2024 – Proceedings

Frontmatter

Keynotes

The Computer in the Sky (Keynote)
Tim Roughgarden
(Columbia University, USA; a16z crypto, USA)

Publisher's Version

Algorithmic Contract Design (Keynote)
Michal Feldman
(Tel Aviv University, Israel)

Publisher's Version

1A (Best Papers)

Single-Source Shortest Paths with Negative Real Weights in Õ(𝑚𝑛^8/9) Time
Jeremy T. Fineman
(Georgetown University, USA)

Publisher's Version

Near Optimal Alphabet-Soundness Tradeoff PCPs
Dor Minzer and Kai Zhe Zheng
(Massachusetts Institute of Technology, USA)

Publisher's Version

Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, and Kewen Wu
(University of California at Berkeley, USA; Nanjing University, China; Peking University, China)

Publisher's Version

2A

Online Edge Coloring Is (Nearly) as Easy as Offline
Joakim Blikstad, Ola Svensson, Radu Vintan, and David Wajc
(KTH Royal Institute of Technology, Stockholm, Sweden; MPI-INF, Germany; EPFL, Lausanne, Switzerland; Technion, Israel)

Publisher's Version

Approximate Earth Mover’s Distance in Truly-Subquadratic Time
Lorenzo Beretta and Aviad Rubinstein
(University of Copenhagen, Copenhagen, Denmark; Stanford University, USA)

Publisher's Version

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
Sayan Bhattacharya, Peter Kiss, Aaron Sidford, and David Wajc
(University of Warwick, United Kingdom; Stanford University, USA; Technion, Israel)

Publisher's Version

Low-Step Multi-commodity Flow Emulators
Bernhard Haeupler, D. Ellis Hershkowitz, Jason Li, Antti Roeyskoe, and Thatchaphol Saranurak
(ETH Zurich, Switzerland; Carnegie Mellon University, USA; Brown University, USA; University of Michigan, USA)

Publisher's Version

Maximum Bipartite Matching in 𝑛^2+𝑜(1) Time via a Combinatorial Algorithm
Julia Chuzhoy and Sanjeev Khanna
(Toyota Technological Institute, Chicago, USA; University of Pennsylvania, USA)

Publisher's Version

2B

Strong Algebras and Radical Sylvester-Gallai Configurations
Rafael Oliveira and Akash Kumar Sengupta
(University of Waterloo, Canada)

Publisher's Version

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
V. Arvind, Abhranil Chatterjee, and Partha Mukhopadhyay
(Institute of Mathematical Sciences, India; Chennai Mathematical Institute, India; Indian Statistical Institute, Kolkata, India)

Publisher's Version

The Minimal Faithful Permutation Degree of Groups without Abelian Normal Subgroups
Bireswar Das and Dhara Thakkar
(IIT Gandhinagar, India)

Publisher's Version

Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring
C. S. Bhargav, Prateek Dwivedi, and Nitin Saxena
(IIT Kanpur, India)

Publisher's Version

On the Power of Homogeneous Algebraic Formulas
Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas
(Université Paris Cité - IMJ-PRG, France; IT University of Copenhagen, Copenhagen, Denmark; University of Copenhagen, Copenhagen, Denmark; Université Savoie Mont Blanc - CNRS - LAMA, France)

Publisher's Version

2C

Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, and Nikos Zarifis
(University of Wisconsin-Madison, USA; University of California at San Diego, USA; University of Texas at Austin, USA)

Publisher's Version

Calibrated Language Models Must Hallucinate
Adam Tauman Kalai and Santosh S. Vempala
(Open AI, USA; Georgia Institute of Technology, USA)

Publisher's Version

Private Graphon Estimation via Sum-of-Squares
Hongjie Chen, Jingqiu Ding, Tommaso D'Orsi, Yiding Hua, Chih-Hung Liu, and David Steurer
(ETH Zurich, Switzerland; Bocconi University, Italy; National Taiwan University, Taiwan)

Publisher's Version

Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
Noah Golowich, Ankur Moitra, and Dhruv Rohatgi
(Massachusetts Institute of Technology, USA)

Publisher's Version

Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances
Spencer Compton and Gregory Valiant
(Stanford University, USA)

Publisher's Version

2D

The Power of Two-Sided Recruitment in Two-Sided Markets
Yang Cai, Christopher Liaw, Aranyak Mehta, and Mingfei Zhao
(Yale University, USA; Google Research, USA)

Publisher's Version

Strategic Budget Selection in a Competitive Autobidding World
Yiding Feng, Brendan Lucier, and Aleksandrs Slivkins
(University of Chicago, USA; Microsoft Research, USA)

Publisher's Version

The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
Nicolo Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi
(University of Milan, Italy; Politecnico di Milano, Italy; University of Ottawa, Canada; Italian Institute of Technology, Italy; Sapienza University of Rome, Italy)

Publisher's Version

Bilateral Trade with Correlated Values
Shahar Dobzinski and Ariel Shaulker
(Weizmann Institute of Science, Israel)

Publisher's Version

No-Regret Learning in Bilateral Trade via Global Budget Balance
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco
(Bocconi University, Italy; Politecnico di Milano, Italy; Sapienza University of Rome, Italy)

Publisher's Version

3A

Knapsack with Small Items in Near-Quadratic Time
Karl Bringmann
(Saarland University, Saarbrücken, Germany; MPI-INF, Germany)

Publisher's Version

0-1 Knapsack in Nearly Quadratic Time
Ce Jin
(Massachusetts Institute of Technology, USA)

Publisher's Version

A Nearly Quadratic-Time FPTAS for Knapsack
Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang
(Zhejiang University, China)

Publisher's Version

(1 − 𝜀)-Approximation of Knapsack in Nearly Quadratic Time
Xiao Mao
(Stanford University, USA)

Publisher's Version

Approximating Partition in Near-Linear Time
Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang
(Zhejiang University, China)

Publisher's Version

Approximating Small Sparse Cuts
Aditya Anand, Euiwoong Lee, Jason Li, and Thatchaphol Saranurak
(University of Michigan, USA; Carnegie Mellon University, USA)

Publisher's Version

Better Coloring of 3-Colorable Graphs
Ken-ichi Kawarabayashi, Mikkel Thorup, and Hirotaka Yoneda
(National Institute of Informatics, Tokyo, Japan; University of Tokyo, Tokyo, Japan; University of Copenhagen, Copenhagen, Denmark)

Publisher's Version

3B

Testing Closeness of Multivariate Distributions via Ramsey Theory
Ilias Diakonikolas, Daniel M. Kane, and Sihan Liu
(University of Wisconsin-Madison, USA; University of California at San Diego, USA)

Publisher's Version

Semidefinite Programs Simulate Approximate Message Passing Robustly
Misha Ivkov and Tselil Schramm
(Stanford University, USA)

Publisher's Version

Planted Clique Conjectures Are Equivalent
Shuichi Hirahara and Nobutaka Shimizu
(National Institute of Informatics, Tokyo, Japan; Tokyo Institute of Technology, Tokyo, Japan)

Publisher's Version

Robust Recovery for Stochastic Block Models, Simplified and Generalized
Sidhanth Mohanty, Prasad Raghavendra, and David X. Wu
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)

Publisher's Version

New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
Aditya Bhaskara, Eric Evert, Vaidehi Srinivas, and Aravindan Vijayaraghavan
(University of Utah, USA; Northwestern University, USA)

Publisher's Version Info

3C

Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation
Brent Waters and David J. Wu
(University of Texas at Austin, USA; NTT Research, USA)

Publisher's Version

A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors
Brent Waters
(University of Texas at Austin, USA; NTT Research, USA)

Publisher's Version

Optimal Load-Balanced Scalable Distributed Agreement
Yuval Gelles and Ilan Komargodski
(Hebrew University of Jerusalem, Israel; NTT Research, USA)

Publisher's Version

Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs
Thomas Debris-Alazard, Pouria Fallahpour, and Damien Stehlé
(Inria - Laboratoire LIX - École Polytechnique, France; ENS Lyon - LIP, France; CryptoLab, France)

Publisher's Version

Batch Proofs Are Statistically Hiding
Nir Bitansky, Chethan Kamath, Omer Paneth, Ron D. Rothblum, and Prashant Nalini Vasudevan
(Tel Aviv University, Israel; IIT Bombay, India; Technion, Israel; National University of Singapore, Singapore)

Publisher's Version

3D

Approximating Maximum Matching Requires Almost Quadratic Time
Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein
(Northeastern University, USA; Stanford University, USA)

Publisher's Version

Structural Complexities of Matching Mechanisms
Yannai A. Gonczarowski and Clayton Thomas
(Harvard University, USA; Microsoft Research, USA)

Publisher's Version

A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations
Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, and Jan Vondrák
(Weizmann Institute of Science, Israel; Stanford University, USA)

Publisher's Version

Limitations of Stochastic Selection Problems with Pairwise Independent Priors
Shaddin Dughmi, Yusuf Hakan Kalayci, and Neel Patel
(University of Southern California, USA)

Publisher's Version

Prophet Inequalities Require Only a Constant Number of Samples
Andrés Cristi and Bruno Ziliotto
(University of Chile, Chile; Center for Mathematical Modeling, Chile; CNRS, France; Paris Dauphine University, France)

Publisher's Version

4A

A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width
Jason Gaitonde and Elchanan Mossel
(Massachusetts Institute of Technology, USA)

Publisher's Version

Nonlinear Dynamics for the Ising Model
Pietro Caputo and Alistair Sinclair
(University Rome III, Italy; University of California at Berkeley, USA)

Publisher's Version

Influences in Mixing Measures
Frederic Koehler, Noam Lifshitz, Dor Minzer, and Elchanan Mossel
(University of Chicago, USA; Hebrew University of Jerusalem, Israel; Massachusetts Institute of Technology, USA)

Publisher's Version

Parallel Sampling via Counting
Nima Anari, Ruiquan Gao, and Aviad Rubinstein
(Stanford University, USA)

Publisher's Version

On the Fourier Coefficients of High-Dimensional Random Geometric Graphs
Kiril Bangachev and Guy Bresler
(Massachusetts Institute of Technology, USA)

Publisher's Version

4B

Classical Simulation of Peaked Shallow Quantum Circuits
Sergey Bravyi, David Gosset, and Yinchen Liu
(IBM Research, USA; University of Waterloo, Canada; Institute for Quantum Computing, Canada; Perimeter Institute for Theoretical Physics, Canada)

Publisher's Version

Quantum and Classical Query Complexities of Functions of Matrices
Ashley Montanaro and Changpeng Shao
(University of Bristol, United Kingdom; Academy of Mathematics and Systems Science at Chinese Academy of Sciences, China)

Publisher's Version

Circuit-to-Hamiltonian from Tensor Networks and Fault Tolerance
Anurag Anshu, Nikolas P. Breuckmann, and Quynh T. Nguyen
(Harvard University, USA; University of Bristol, United Kingdom)

Publisher's Version

Quantum Time-Space Tradeoffs for Matrix Problems
Paul Beame, Niels Kornerup, and Michael Whitmeyer
(University of Washington, USA; University of Texas at Austin, USA)

Publisher's Version

Quadratic Lower Bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
Saeed Mehraban and Mehrdad Tahmasbi
(Tufts University, USA; University of Illinois at Urbana-Champaign, USA)

Publisher's Version

4C

Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography
Yilei Chen and Jiatu Li
(Tsinghua University, China; Shanghai Qi Zhi Institute, Shanghai, China; Massachusetts Institute of Technology, USA)

Publisher's Version

Communication Lower Bounds for Collision Problems via Density Increment Arguments
Guangxu Yang and Jiapeng Zhang
(University of Southern California, USA)

Publisher's Version

Lower Bounds for Regular Resolution over Parities
Klim Efremenko, Michal Garlík, and Dmitry Itsykson
(Ben-Gurion University of the Negev, Israel; Imperial College London, United Kingdom)

Publisher's Version

XOR Lemmas for Communication via Marginal Information
Siddharth Iyer and Anup Rao
(University of Washington, USA)

Publisher's Version

Beating Brute Force for Compression Problems
Shuichi Hirahara, Rahul Ilango, and R. Ryan Williams
(National Institute of Informatics, Tokyo, Japan; Massachusetts Institute of Technology, USA)

Publisher's Version

4D

Optimization with Pattern-Avoiding Input
Benjamin Aram Berendsohn, László Kozma, and Michal Opler
(Freie Universität Berlin, Berlin, Germany; Czech Technical University, Prague, Czechia)

Publisher's Version

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Peter Gartland, Daniel Lokshtanov, Tomáš Masařík, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski
(University of California at Santa Barbara, USA; University of Warsaw, Poland; IT University of Copenhagen, Copenhagen, Denmark; Warsaw University of Technology, Poland)

Publisher's Version

Packing Even Directed Circuits Quarter-Integrally
Maximilian Gorsky, Ken-ichi Kawarabayashi, Stephan Kreutzer, and Sebastian Wiederrecht
(TU Berlin, Berlin, Germany; National Institute of Informatics, Tokyo, Japan; University of Tokyo, Tokyo, Japan; Institute for Basic Science, Daejeon, South Korea)

Publisher's Version

Edge-Disjoint Paths in Eulerian Digraphs
Dario Giuliano Cavallaro, Ken-ichi Kawarabayashi, and Stephan Kreutzer
(TU Berlin, Berlin, Germany; National Institute of Informatics, Tokyo, Japan; University of Tokyo, Tokyo, Japan)

Publisher's Version

A Flat Wall Theorem for Matching Minors in Bipartite Graphs
Archontia C. Giannopoulou and Sebastian Wiederrecht
(National and Kapodistrian University of Athens, Athens, Greece; Institute for Basic Science, Daejeon, South Korea)

Publisher's Version

5A

Generalized GM-MDS: Polynomial Codes Are Higher Order MDS
Joshua Brakensiek, Manik Dhar, and Sivakanth Gopi
(Independent, USA; Massachusetts Institute of Technology, USA; Microsoft Research, USA)

Publisher's Version

AG Codes Achieve List Decoding Capacity over Constant-Sized Fields
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, and Zihan Zhang
(Independent, USA; Massachusetts Institute of Technology, USA; Microsoft Research, USA; Ohio State University, USA)

Publisher's Version

Constant Query Local Decoding against Deletions Is Impossible
Meghal Gupta
(University of California at Berkeley, USA)

Publisher's Version

Local Correction of Linear Functions over the Boolean Cube
Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, and Madhu Sudan
(Harvard University, USA; Aarhus University, Aarhus, Denmark; University of Copenhagen, Copenhagen, Denmark)

Publisher's Version

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes
Pravesh K. Kothari and Peter Manohar
(Institute for Advanced Study, Princeton, USA; Princeton University, USA; Carnegie Mellon University, USA)

Publisher's Version

Explicit Two-Sided Unique-Neighbor Expanders
Jun-Ting Hsieh, Theo McKenzie, Sidhanth Mohanty, and Pedro Paredes
(Carnegie Mellon University, USA; Stanford University, USA; Massachusetts Institute of Technology, USA; Princeton University, USA)

Publisher's Version

5B

Data-Dependent LSH for the Earth Mover’s Distance
Rajesh Jayaram, Erik Waingarten, and Tian Zhang
(Google Research, USA; University of Pennsylvania, USA)

Publisher's Version

Polylog-Competitive Deterministic Local Routing and Scheduling
Bernhard Haeupler, Shyamal Patel, Antti Roeyskoe, Cliff Stein, and Goran Zuzic
(ETH Zurich, Switzerland; Carnegie Mellon University, USA; Columbia University, USA; Google Research, Switzerland)

Publisher's Version

Connectivity Labeling and Routing with Multiple Vertex Failures
Merav Parter, Asaf Petruschka, and Seth Pettie
(Weizmann Institute of Science, Israel; University of Michigan, USA)

Publisher's Version

Optimal Multi-pass Lower Bounds for MST in Dynamic Streams
Sepehr Assadi, Gillat Kol, and Zhijun Zhang
(University of Waterloo, Canada; Rutgers University, USA; Princeton University, USA)

Publisher's Version

O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set
Sepehr Assadi, Christian Konrad, Kheeran K. Naidu, and Janani Sundaresan
(University of Waterloo, Canada; Rutgers University, USA; University of Bristol, United Kingdom)

Publisher's Version

5C

The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True
Andreas Björklund and Petteri Kaski
(IT University of Copenhagen, Copenhagen, Denmark; Aalto University, Finland)

Publisher's Version

A Stronger Connection between the Asymptotic Rank Conjecture and the Set Cover Conjecture
Kevin Pratt
(New York University, USA)

Publisher's Version

Equality Cases of the Alexandrov–Fenchel Inequality Are Not in the Polynomial Hierarchy
Swee Hong Chan and Igor Pak
(Rutgers University, USA; University of California at Los Angeles, USA)

Publisher's Version

Semigroup Algorithmic Problems in Metabelian Groups
Ruiwen Dong
(Saarland University, Saarbrücken, Germany)

Publisher's Version

The Complexity of Computing KKT Solutions of Quadratic Programs
John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani
(University of Liverpool, United Kingdom; University of Oxford, United Kingdom; Alan Turing Institute, United Kingdom)

Publisher's Version

Minimum Star Partitions of Simple Polygons in Polynomial Time
Mikkel Abrahamsen, Joakim Blikstad, André Nusser, and Hanwen Zhang
(University of Copenhagen, Copenhagen, Denmark; KTH Royal Institute of Technology, Stockholm, Sweden; MPI-INF, Germany)

Publisher's Version

6A

Revisiting Local Computation of PageRank: Simple and Optimal
Hanzhi Wang, Zhewei Wei, Ji-Rong Wen, and Mingji Yang
(Renmin University of China, China)

Publisher's Version

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams, and Yinzhan Xu
(Morgan Stanley Research, Canada; Massachusetts Institute of Technology, USA)

Publisher's Version

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, and Raghu Meka
(Weizmann Institute of Science, Israel; University of Illinois at Urbana-Champaign, USA; University of California at San Diego, USA; University of California at Los Angeles, USA)

Publisher's Version

Nearly Optimal Fault Tolerant Distance Oracle
Dipan Dey and Manoj Gupta
(IIT Gandhinagar, India)

Publisher's Version

Almost Linear Size Edit Distance Sketch
Michal Koucký and Michael E. Saks
(Charles University, Prague, Czechia; Rutgers University, USA)

Publisher's Version

6B

Commitments from Quantum One-Wayness
Dakshita Khurana and Kabir Tomer
(University of Illinois at Urbana-Champaign, USA)

Publisher's Version

A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography
Alex Lombardi, Fermi Ma, and John Wright
(Princeton University, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, USA)

Publisher's Version

Two Prover Perfect Zero Knowledge for MIP*
Kieran Mastel and William Slofstra
(University of Waterloo, Canada)

Publisher's Version

How to Use Quantum Indistinguishability Obfuscation
Andrea Coladangelo and Sam Gunn
(University of Washington, USA; University of California at Berkeley, USA)

Publisher's Version

Quantum State Obfuscation from Classical Oracles
James Bartusek, Zvika Brakerski, and Vinod Vaikuntanathan
(University of California at Berkeley, USA; Weizmann Institute of Science, Israel; Massachusetts Institute of Technology, USA)

Publisher's Version

Nonlocality under Computational Assumptions
Grzegorz Gluch, Khashayar Barooti, Alexandru Gheorghiu, and Marc-Olivier Renou
(EPFL, Lausanne, Switzerland; Aztec Labs, United Kingdom; Chalmers University of Technology, Sweden; Inria - Université Paris-Saclay - CPHT - École Polytechnique - Institut Polytechnique de Paris, France)

Publisher's Version

6C

Detecting Low-Degree Truncation
Anindya De, Huan Li, Shivam Nadimpalli, and Rocco A. Servedio
(University of Pennsylvania, USA; Columbia University, USA)

Publisher's Version

Optimal Non-adaptive Tolerant Junta Testing via Local Estimators
Shivam Nadimpalli and Shyamal Patel
(Columbia University, USA)

Publisher's Version

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
Xi Chen, Yumou Fei, and Shyamal Patel
(Columbia University, USA; Peking University, China)

Publisher's Version

On the Power of Interactive Proofs for Learning
Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, and Igor Shinkar
(University of Cambridge, United Kingdom; Simon Fraser University, Canada; Qualcomm, Canada)

Publisher's Version

Complexity-Theoretic Implications of Multicalibration
Sílvia Casacuberta, Cynthia Dwork, and Salil Vadhan
(University of Oxford, United Kingdom; Harvard University, USA)

Publisher's Version

6D

Local Geometry of NAE-SAT Solutions in the Condensation Regime
Allan Sly and Youngtak Sohn
(Princeton University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Info

Trickle-Down in Localization Schemes and Applications
Nima Anari, Frederic Koehler, and Thuy-Duong Vuong
(Stanford University, USA; University of Chicago, USA)

Publisher's Version

Optimal Embedding Dimension for Sparse Subspace Embeddings
Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong, and Mark Rudelson
(University of Michigan, USA)

Publisher's Version

Solving Dense Linear Systems Faster Than via Preconditioning
Michał Dereziński and Jiaming Yang
(University of Michigan, USA)

Publisher's Version

Improving the Bit Complexity of Communication for Distributed Convex Optimization
Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, and Guanghao Ye
(Massachusetts Institute of Technology, USA; University of Washington, USA; Microsoft Research, USA; Carnegie Mellon University, USA)

Publisher's Version

7A

Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
Xiao Mao
(Stanford University, USA)

Publisher's Version

Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval
William Kuszmaul and Stefan Walzer
(Harvard University, USA; KIT, Karlsruhe, Germany)

Publisher's Version

Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow
Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, and Maximilian Probst Gutenberg
(Carnegie Mellon University, USA; ETH Zurich, Switzerland; Institute for Advanced Study, Princeton, USA)

Publisher's Version

A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications
Rasmus Kyng, Simon Meierhans, and Maximilian Probst Gutenberg
(ETH Zurich, Switzerland)

Publisher's Version

Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case Time
Mohsen Ghaffari and Christoph Grunau
(Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland)

Publisher's Version

7B

Settling the Communication Complexity of VCG-Based Mechanisms for All Approximation Guarantees
Frederick Qiu and S. Matthew Weinberg
(Princeton University, USA)

Publisher's Version

PPAD-Membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization
Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, and Alexandros Hollender
(University of Edinburgh, United Kingdom; Aarhus University, Aarhus, Denmark; University of Oxford, United Kingdom)

Publisher's Version

From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich
(University of California at Berkeley, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria
Binghui Peng and Aviad Rubinstein
(Columbia University, USA; Stanford University, USA)

Publisher's Version

Fair Division via Quantile Shares
Yakov Babichenko, Michal Feldman, Ron Holzman, and Vishnu V. Narayan
(Technion, Israel; Tel Aviv University, Israel)

Publisher's Version

Prophet Inequalities with Cancellation Costs
Farbod Ekbatani, Rad Niazadeh, Pranav Nuti, and Jan Vondrák
(University of Chicago, USA; Stanford University, USA)

Publisher's Version

7C

Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
Nicholas Harvey and Arvin Sahami
(University of British Columbia, Canada)

Publisher's Version

Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)
James Cook and Ian Mertz
(Unaffiliated, Canada; University of Warwick, United Kingdom)

Publisher's Version

Locality Bounds for Sampling Hamming Slices
Daniel M. Kane, Anthony Ostuni, and Kewen Wu
(University of California at San Diego, USA; University of California at Berkeley, USA)

Publisher's Version

No Complete Problem for Constant-Cost Randomized Communication
Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, and Pooya Hatami
(Ohio State University, USA; Hebrew University of Jerusalem, Israel; EPFL, Lausanne, Switzerland)

Publisher's Version

Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication
Zander Kelley, Shachar Lovett, and Raghu Meka
(University of Illinois at Urbana-Champaign, USA; University of California at San Diego, USA; University of California at Los Angeles, USA)

Publisher's Version

7D

An Area Law for the Maximally-Mixed Ground State in Arbitrarily Degenerate Systems with Good AGSP
Itai Arad, Raz Firanko, and Rahul Jain
(Centre for Quantum Technologies, Singapore; Technion, Israel; National University of Singapore, Singapore)

Publisher's Version

Local Minima in Quantum Systems
Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, and Leo Zhou
(California Institute of Technology, USA; AWS Center for Quantum Computing, USA; Google Quantum AI, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography
Sitan Chen, Jerry Li, and Allen Liu
(Harvard University, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Learning Shallow Quantum Circuits
Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean
(California Institute of Technology, USA; Google Quantum AI, USA; University of California at Berkeley, USA; University of California at Davis, USA; Harvard University, USA)

Publisher's Version

Improved Stabilizer Estimation via Bell Difference Sampling
Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang
(University of Texas at Austin, USA; Simons Institute for the Theory of Computing, Berkeley, USA; Rice University, USA)

Publisher's Version

8A

Computing a Fixed Point of Contraction Maps in Polynomial Queries
Xi Chen, Yuhao Li, and Mihalis Yannakakis
(Columbia University, USA)

Publisher's Version

Self-Improvement for Circuit-Analysis Problems
R. Ryan Williams
(Massachusetts Institute of Technology, USA)

Publisher's Version

Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication
Benjamin Rossman
(Duke University, USA)

Publisher's Version

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
Tuomas Hakoniemi, Nutan Limaye, and Iddo Tzameret
(University of Helsinki, Helsinki, Finland; IT University of Copenhagen, Copenhagen, Denmark; Imperial College London, United Kingdom)

Publisher's Version

Black-Box PPP Is Not Turing-Closed
Noah Fleming, Stefan Grosser, Toniann Pitassi, and Robert Robere
(Memorial University of Newfoundland, Canada; McGill University, Canada; Columbia University, USA)

Publisher's Version

8B

Product Mixing in Compact Lie Groups
David Ellis, Guy Kindler, Noam Lifshitz, and Dor Minzer
(University of Bristol, United Kingdom; Hebrew University of Jerusalem, Israel; Massachusetts Institute of Technology, USA)

Publisher's Version

On Approximability of Satisfiable k-CSPs: IV
Amey Bhangale, Subhash Khot, and Dor Minzer
(University of California at Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
Shuichi Hirahara and Naoto Ohsaka
(National Institute of Informatics, Tokyo, Japan; CyberAgent, Japan)

Publisher's Version

Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
Uriya A. First and Tali Kaufman
(University of Haifa, Israel; Bar-Ilan University, Israel)

Publisher's Version

Randomly Punctured Reed–Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields
Omar Alrabiah, Venkatesan Guruswami, and Ray Li
(University of California at Berkeley, USA; Santa Clara University, USA)

Publisher's Version

8C

Learning Quantum Hamiltonians at Any Temperature in Polynomial Time
Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)

Publisher's Version

An Efficient Quantum Parallel Repetition Theorem and Applications
John Bostanci, Luowen Qian, Nicholas Spooner, and Henry Yuen
(Columbia University, USA; Boston University, USA; University of Warwick, United Kingdom; New York University, USA)

Publisher's Version

The Power of Adaptivity in Quantum Query Algorithms
Uma Girish, Makrand Sinha, Avishay Tal, and Kewen Wu
(Princeton University, USA; University of Illinois at Urbana-Champaign, USA; University of California at Berkeley, USA)

Publisher's Version

On the Pauli Spectrum of QAC0
Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen
(Columbia University, USA; University of California at Berkeley, USA)

Publisher's Version

Approaching the Quantum Singleton Bound with Approximate Error Correction
Thiago Bergamaschi, Louis Golowich, and Sam Gunn
(University of California at Berkeley, USA)

Publisher's Version

8D

Counting Small Induced Subgraphs with Edge-Monotone Properties
Simon Döring, Dániel Marx, and Philip Wellnitz
(MPI-INF, Germany; Saarbrücken Graduate School of Computer Science, Saarbrücken, Germany; Saarland Informatics Campus, Saarbrücken, Germany; CISPA Helmholtz Center for Information Security, Germany)

Publisher's Version

Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes
Yury Makarychev, Naren Sarayu Manoj, and Max Ovsiankin
(Toyota Technological Institute, Chicago, USA)

Publisher's Version

Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic Rankwidth
Tuukka Korhonen and Marek Sokołowski
(University of Bergen, Norway; University of Warsaw, Poland)

Publisher's Version

Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
Jan Dreier, Nikolas Mählmann, and Szymon Toruńczyk
(TU Wien, Austria; University of Bremen, Bremen, Germany; University of Warsaw, Poland)

Publisher's Version

A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column
Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, and László A. Végh
(CWI, Amsterdam, Netherlands; Georgia Institute of Technology, USA; London School of Economics, United Kingdom)

Publisher's Version Info

9A (Best Student Papers)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
Ce Jin and Yinzhan Xu
(Massachusetts Institute of Technology, USA)

Publisher's Version

Relaxed Local Correctability from Local Testing
Vinayak M. Kumar and Geoffrey Mon
(University of Texas at Austin, USA)

Publisher's Version

10A

On Optimal Coreset Construction for Euclidean (k,z)-Clustering
Lingxiao Huang, Jian Li, and Xuan Wu
(Nanjing University, China; Tsinghua University, China)

Publisher's Version

Understanding the Cluster Linear Program for Correlation Clustering
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, and Lukas Vogl
(Boston College, USA; Google Research, France; University of Michigan, USA; Nanjing University, China; CNRS - Université Grenoble Alpes, France; EPFL, Lausanne, Switzerland)

Publisher's Version Info

Combinatorial Correlation Clustering
Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, and Hanwen Zhang
(Google Research, France; University of Copenhagen, Copenhagen, Denmark; University of Warsaw, Poland)

Publisher's Version Info

Random-Order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals
Calum MacRury and Will Ma
(Columbia University, USA)

Publisher's Version Info

Prize-Collecting Steiner Tree: A 1.79 Approximation
Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Mohammad Mahdavi
(University of Maryland, USA)

Publisher's Version

10B

Reconfiguration of Basis Pairs in Regular Matroids
Kristóf Bérczi, Bence Mátravölgyi, and Tamás Schwarcz
(University of Eötvös Loránd, Hungary; ETH Zurich, Switzerland)

Publisher's Version

Sparsifying Generalized Linear Models
Arun Jambulapati, James R. Lee, Yang P. Liu, and Aaron Sidford
(Simons Institute for the Theory of Computing, Berkeley, USA; University of Washington, USA; Institute for Advanced Study, Princeton, USA; Stanford University, USA)

Publisher's Version Video

Sampling Balanced Forests of Grids in Polynomial Time
Sarah Cannon, Wesley Pegden, and Jamie Tucker-Foltz
(Claremont McKenna College, USA; Carnegie Mellon University, USA; Harvard University, USA)

Publisher's Version

Sampling Proper Colorings on Line Graphs Using (1+o(1))Δ Colors
Yulin Wang, Chihao Zhang, and Zihan Zhang
(Shanghai Jiao Tong University, China; SOKENDAI, Japan)

Publisher's Version

Hypergraph Unreliability in Quasi-Polynomial Time
Ruoxu Cen, Jason Li, and Debmalya Panigrahi
(Duke University, USA; Carnegie Mellon University, USA)

Publisher's Version

10C

Memory Checking Requires Logarithmic Overhead
Elette Boyle, Ilan Komargodski, and Neekon Vafa
(Reichman University, Israel; NTT Research, USA; Hebrew University of Jerusalem, Israel; Massachusetts Institute of Technology, USA)

Publisher's Version

Perfect Zero-Knowledge PCPs for #P
Tom Gur, Jack O'Connor, and Nicholas Spooner
(University of Cambridge, United Kingdom; University of Warwick, United Kingdom; New York University, USA)

Publisher's Version

One-Way Functions and Zero Knowledge
Shuichi Hirahara and Mikito Nanashima
(National Institute of Informatics, Tokyo, Japan; Tokyo Institute of Technology, Tokyo, Japan)

Publisher's Version

Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem
Akshima, Tyler Besselman, Siyao Guo, Zhiye Xie, and Yuping Ye
(NYU Shanghai, China; East China Normal University, China)

Publisher's Version

SNARGs under LWE via Propositional Proofs
Zhengzhong Jin, Yael Kalai, Alex Lombardi, and Vinod Vaikuntanathan
(Northeastern University, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Princeton University, USA)

Publisher's Version

10D

On the Communication Complexity of Approximate Pattern Matching
Tomasz Kociumaka, Jakob Nogler, and Philip Wellnitz
(MPI-INF, Germany; Saarland Informatics Campus, Saarbrücken, Germany; ETH Zurich, Switzerland)

Publisher's Version

Local Borsuk-Ulam, Stability, and Replicability
Zachary Chase, Bogdan Chornomaz, Shay Moran, and Amir Yehudayoff
(Technion, Israel; Google Research, Israel; University of Copenhagen, Copenhagen, Denmark)

Publisher's Version

A New Information Complexity Measure for Multi-pass Streaming with Applications
Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, and Jiapeng Zhang
(Princeton University, USA; Rutgers University, USA; Shenzhen Research Institute of Big Data, China; Shanghai Jiao Tong University, China; Carnegie Mellon University, USA; University of Southern California, USA)

Publisher's Version

New Graph and Hypergraph Container Lemmas with Applications in Property Testing
Eric Blais and Cameron Seth
(University of Waterloo, Canada)

Publisher's Version

Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
John Kallaugher, Ojas Parekh, and Nadezhda Voronova
(Sandia National Laboratories, USA; Boston University, USA)

Publisher's Version

11A

Proof of the Density Threshold Conjecture for Pinwheel Scheduling
Akitoshi Kawamura
(Kyoto University, Kyoto, Japan)

Publisher's Version

Constrained Submodular Maximization via New Bounds for DR-Submodular Functions
Niv Buchbinder and Moran Feldman
(Tel Aviv University, Israel; University of Haifa, Israel)

Publisher's Version

Optimal Online Discrepancy Minimization
Janardhan Kulkarni, Victor Reis, and Thomas Rothvoss
(Microsoft Research, USA; Institute for Advanced Study, Princeton, USA; University of Washington, USA)

Publisher's Version

Supermodular Approximation of Norms and Applications
Thomas Kesselheim, Marco Molinaro, and Sahil Singla
(University of Bonn, Bonn, Germany; PUC-Rio, Brazil; Georgia Institute of Technology, USA)

Publisher's Version

Ghost Value Augmentation for k-Edge-Connectivity
D. Ellis Hershkowitz, Nathan Klein, and Rico Zenklusen
(Brown University, USA; Institute for Advanced Study, Princeton, USA; ETH Zurich, Switzerland)

Publisher's Version

11B

Breaking the VLB Barrier for Oblivious Reconfigurable Networks
Tegan Wilson, Daniel Amir, Nitika Saran, Robert Kleinberg, Vishal Shrivastav, and Hakim Weatherspoon
(Cornell University, USA; Purdue University, USA)

Publisher's Version

Lenzen’s Distributed Routing Generalized: A Full Characterization of Constant-Time Routability
Mohsen Ghaffari and Brandon Wang
(Massachusetts Institute of Technology, USA)

Publisher's Version

Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping
Mohsen Ghaffari and Christoph Grunau
(Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland)

Publisher's Version

No Distributed Quantum Advantage for Approximate Graph Coloring
Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, and Jukka Suomela
(TU Munich, Germany; Munich Center for Quantum Science and Technology, Germany; Aalto University, Finland; Bocconi University, Italy; Indian Institute of Science, India; University of Freiburg, Freiburg, Germany; Nagoya University, Nagoya, Japan; Inria, France; Université Paris-Saclay, France; Institut Polytechnique de Paris, France)

Publisher's Version

Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond
Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, and Peilin Zhong
(Google, United Kingdom; Carnegie Mellon University, USA; Google Research, USA)

Publisher's Version

11C

Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs
Pravesh K. Kothari, Aaron Potechin, and Jeff Xu
(Carnegie Mellon University, USA; University of Chicago, USA)

Publisher's Version

Semidefinite Programming and Linear Equations vs. Homomorphism Problems
Lorenzo Ciardo and Stanislav Živný
(University of Oxford, United Kingdom)

Publisher's Version

How Random CSPs Fool Hierarchies
Siu On Chan, Hiu Tsun Ng, and Sijin Peng
(Unaffiliated, Hong Kong, China; Chinese University of Hong Kong, China; Tsinghua University, China)

Publisher's Version

Swap Cosystolic Expansion
Yotam Dikstein and Irit Dinur
(Institute for Advanced Study, Princeton, USA; Weizmann Institute of Science, Israel)

Publisher's Version

Agreement Theorems for High Dimensional Expanders in the Low Acceptance Regime: The Role of Covers
Yotam Dikstein and Irit Dinur
(Institute for Advanced Study, Princeton, USA; Weizmann Institute of Science, Israel)

Publisher's Version

Characterizing Direct Product Testing via Coboundary Expansion
Mitali Bafna and Dor Minzer
(Massachusetts Institute of Technology, USA)

Publisher's Version

11D

Symmetric Exponential Time Requires Near-Maximum Circuit Size
Lijie Chen, Shuichi Hirahara, and Hanlin Ren
(University of California at Berkeley, USA; National Institute of Informatics, Tokyo, Japan; University of Oxford, United Kingdom)

Publisher's Version

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
Zeyong Li
(National University of Singapore, Singapore)

Publisher's Version

Random (log 𝑛)-CNF Are Hard for Cutting Planes (Again)
Dmitry Sokolov
(EPFL, Lausanne, Switzerland)

Publisher's Version

Hardness Condensation by Restriction
Mika Göös, Ilan Newman, Artur Riazanov, and Dmitry Sokolov
(EPFL, Lausanne, Switzerland; University of Haifa, Israel)

Publisher's Version

Explicit Codes for Poly-Size Circuits and Functions That Are Hard to Sample on Low Entropy Distributions
Ronen Shaltiel and Jad Silbak
(University of Haifa, Israel; Northeastern University, USA)

Publisher's Version

Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL
Dean Doron, Edward Pyne, and Roei Tell
(Ben-Gurion University of the Negev, Israel; Massachusetts Institute of Technology, USA; University of Toronto, Canada)

Publisher's Version

proc time: 27.74