STOC 2024
56th Annual ACM Symposium on Theory of Computing (STOC 2024)
Powered by
Conference Publishing Consulting

56th Annual ACM Symposium on Theory of Computing (STOC 2024), June 24–28, 2024, Vancouver, BC, Canada

STOC 2024 – Proceedings

Contents - Abstracts - Authors

Frontmatter

Title Page
Welcome from the Program Chair
STOC 2024 Conference Organization
Sponsors

Keynotes

The Computer in the Sky (Keynote)
Tim Roughgarden ORCID logo
(Columbia University, USA; a16z crypto, USA)
Publisher's Version
Algorithmic Contract Design (Keynote)
Michal Feldman ORCID logo
(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 ORCID logo
(Georgetown University, USA)
Publisher's Version
Near Optimal Alphabet-Soundness Tradeoff PCPs
Dor Minzer ORCID logo and Kai Zhe Zheng ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
Venkatesan Guruswami ORCID logo, Bingkai Lin ORCID logo, Xuandi RenORCID logo, Yican Sun ORCID logo, and Kewen Wu ORCID logo
(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 ORCID logo, Ola Svensson ORCID logo, Radu Vintan ORCID logo, and David Wajc ORCID logo
(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 ORCID logo and Aviad Rubinstein ORCID logo
(University of Copenhagen, Copenhagen, Denmark; Stanford University, USA)
Publisher's Version
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
Sayan Bhattacharya ORCID logo, Peter Kiss ORCID logo, Aaron Sidford ORCID logo, and David Wajc ORCID logo
(University of Warwick, United Kingdom; Stanford University, USA; Technion, Israel)
Publisher's Version
Low-Step Multi-commodity Flow Emulators
Bernhard Haeupler ORCID logo, D. Ellis Hershkowitz ORCID logo, Jason Li ORCID logo, Antti Roeyskoe ORCID logo, and Thatchaphol SaranurakORCID logo
(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 ORCID logo and Sanjeev Khanna ORCID logo
(Toyota Technological Institute, Chicago, USA; University of Pennsylvania, USA)
Publisher's Version

2B

Strong Algebras and Radical Sylvester-Gallai Configurations
Rafael Oliveira ORCID logo and Akash Kumar Sengupta ORCID logo
(University of Waterloo, Canada)
Publisher's Version
Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
V. Arvind ORCID logo, Abhranil Chatterjee ORCID logo, and Partha MukhopadhyayORCID logo
(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 ORCID logo and Dhara Thakkar ORCID logo
(IIT Gandhinagar, India)
Publisher's Version
Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring
C. S. BhargavORCID logo, Prateek DwivediORCID logo, and Nitin SaxenaORCID logo
(IIT Kanpur, India)
Publisher's Version
On the Power of Homogeneous Algebraic Formulas
Hervé Fournier ORCID logo, Nutan Limaye ORCID logo, Srikanth Srinivasan ORCID logo, and Sébastien Tavenas ORCID logo
(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 ORCID logo, Daniel M. KaneORCID logo, Vasilis Kontonis ORCID logo, Sihan LiuORCID logo, and Nikos Zarifis ORCID logo
(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 ORCID logo and Santosh S. Vempala ORCID logo
(Open AI, USA; Georgia Institute of Technology, USA)
Publisher's Version
Private Graphon Estimation via Sum-of-Squares
Hongjie Chen ORCID logo, Jingqiu Ding ORCID logo, Tommaso D'Orsi ORCID logo, Yiding Hua ORCID logo, Chih-Hung Liu ORCID logo, and David Steurer ORCID logo
(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 GolowichORCID logo, Ankur Moitra ORCID logo, and Dhruv Rohatgi ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances
Spencer Compton ORCID logo and Gregory Valiant ORCID logo
(Stanford University, USA)
Publisher's Version

2D

The Power of Two-Sided Recruitment in Two-Sided Markets
Yang Cai ORCID logo, Christopher Liaw ORCID logo, Aranyak Mehta ORCID logo, and Mingfei Zhao ORCID logo
(Yale University, USA; Google Research, USA)
Publisher's Version
Strategic Budget Selection in a Competitive Autobidding World
Yiding Feng ORCID logo, Brendan Lucier ORCID logo, and Aleksandrs Slivkins ORCID logo
(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 ORCID logo, Tommaso Cesari ORCID logo, Roberto Colomboni ORCID logo, Federico Fusco ORCID logo, and Stefano Leonardi ORCID logo
(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 ORCID logo and Ariel Shaulker ORCID logo
(Weizmann Institute of Science, Israel)
Publisher's Version
No-Regret Learning in Bilateral Trade via Global Budget Balance
Martino Bernasconi ORCID logo, Matteo Castiglioni ORCID logo, Andrea Celli ORCID logo, and Federico Fusco ORCID logo
(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 ORCID logo
(Saarland University, Saarbrücken, Germany; MPI-INF, Germany)
Publisher's Version
0-1 Knapsack in Nearly Quadratic Time
Ce JinORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
A Nearly Quadratic-Time FPTAS for Knapsack
Lin Chen ORCID logo, Jiayi Lian ORCID logo, Yuchen Mao ORCID logo, and Guochuan Zhang ORCID logo
(Zhejiang University, China)
Publisher's Version
(1 − 𝜀)-Approximation of Knapsack in Nearly Quadratic Time
Xiao Mao ORCID logo
(Stanford University, USA)
Publisher's Version
Approximating Partition in Near-Linear Time
Lin Chen ORCID logo, Jiayi Lian ORCID logo, Yuchen Mao ORCID logo, and Guochuan Zhang ORCID logo
(Zhejiang University, China)
Publisher's Version
Approximating Small Sparse Cuts
Aditya Anand ORCID logo, Euiwoong Lee ORCID logo, Jason Li ORCID logo, and Thatchaphol SaranurakORCID logo
(University of Michigan, USA; Carnegie Mellon University, USA)
Publisher's Version
Better Coloring of 3-Colorable Graphs
Ken-ichi Kawarabayashi ORCID logo, Mikkel Thorup ORCID logo, and Hirotaka Yoneda ORCID logo
(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 ORCID logo, Daniel M. KaneORCID logo, and Sihan LiuORCID logo
(University of Wisconsin-Madison, USA; University of California at San Diego, USA)
Publisher's Version
Semidefinite Programs Simulate Approximate Message Passing Robustly
Misha Ivkov ORCID logo and Tselil Schramm ORCID logo
(Stanford University, USA)
Publisher's Version
Planted Clique Conjectures Are Equivalent
Shuichi Hirahara ORCID logo and Nobutaka Shimizu ORCID logo
(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 ORCID logo, Prasad RaghavendraORCID logo, and David X. Wu ORCID logo
(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 ORCID logo, Eric Evert ORCID logo, Vaidehi Srinivas ORCID logo, and Aravindan Vijayaraghavan ORCID logo
(University of Utah, USA; Northwestern University, USA)
Publisher's Version Info

3C

Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation
Brent Waters ORCID logo and David J. Wu ORCID logo
(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 ORCID logo
(University of Texas at Austin, USA; NTT Research, USA)
Publisher's Version
Optimal Load-Balanced Scalable Distributed Agreement
Yuval Gelles ORCID logo and Ilan Komargodski ORCID logo
(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 ORCID logo, Pouria Fallahpour ORCID logo, and Damien Stehlé ORCID logo
(Inria - Laboratoire LIX - École Polytechnique, France; ENS Lyon - LIP, France; CryptoLab, France)
Publisher's Version
Batch Proofs Are Statistically Hiding
Nir Bitansky ORCID logo, Chethan Kamath ORCID logo, Omer Paneth ORCID logo, Ron D. Rothblum ORCID logo, and Prashant Nalini Vasudevan ORCID logo
(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 ORCID logo, Mohammad Roghani ORCID logo, and Aviad Rubinstein ORCID logo
(Northeastern University, USA; Stanford University, USA)
Publisher's Version
Structural Complexities of Matching Mechanisms
Yannai A. GonczarowskiORCID logo and Clayton Thomas ORCID logo
(Harvard University, USA; Microsoft Research, USA)
Publisher's Version
A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations
Shahar Dobzinski ORCID logo, Wenzheng Li ORCID logo, Aviad Rubinstein ORCID logo, and Jan Vondrák ORCID logo
(Weizmann Institute of Science, Israel; Stanford University, USA)
Publisher's Version
Limitations of Stochastic Selection Problems with Pairwise Independent Priors
Shaddin Dughmi ORCID logo, Yusuf Hakan Kalayci ORCID logo, and Neel Patel ORCID logo
(University of Southern California, USA)
Publisher's Version
Prophet Inequalities Require Only a Constant Number of Samples
Andrés CristiORCID logo and Bruno Ziliotto ORCID logo
(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 ORCID logo and Elchanan Mossel ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
Nonlinear Dynamics for the Ising Model
Pietro Caputo ORCID logo and Alistair Sinclair ORCID logo
(University Rome III, Italy; University of California at Berkeley, USA)
Publisher's Version
Influences in Mixing Measures
Frederic Koehler ORCID logo, Noam Lifshitz ORCID logo, Dor Minzer ORCID logo, and Elchanan Mossel ORCID logo
(University of Chicago, USA; Hebrew University of Jerusalem, Israel; Massachusetts Institute of Technology, USA)
Publisher's Version
Parallel Sampling via Counting
Nima Anari ORCID logo, Ruiquan Gao ORCID logo, and Aviad Rubinstein ORCID logo
(Stanford University, USA)
Publisher's Version
On the Fourier Coefficients of High-Dimensional Random Geometric Graphs
Kiril Bangachev ORCID logo and Guy Bresler ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version

4B

Classical Simulation of Peaked Shallow Quantum Circuits
Sergey Bravyi ORCID logo, David Gosset ORCID logo, and Yinchen Liu ORCID logo
(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 ORCID logo and Changpeng Shao ORCID logo
(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 ORCID logo, Nikolas P. Breuckmann ORCID logo, and Quynh T. Nguyen ORCID logo
(Harvard University, USA; University of Bristol, United Kingdom)
Publisher's Version
Quantum Time-Space Tradeoffs for Matrix Problems
Paul Beame ORCID logo, Niels Kornerup ORCID logo, and Michael Whitmeyer ORCID logo
(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 ORCID logo and Mehrdad Tahmasbi ORCID logo
(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 ORCID logo and Jiatu Li ORCID logo
(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 ORCID logo and Jiapeng Zhang ORCID logo
(University of Southern California, USA)
Publisher's Version
Lower Bounds for Regular Resolution over Parities
Klim Efremenko ORCID logo, Michal Garlík ORCID logo, and Dmitry Itsykson ORCID logo
(Ben-Gurion University of the Negev, Israel; Imperial College London, United Kingdom)
Publisher's Version
XOR Lemmas for Communication via Marginal Information
Siddharth Iyer ORCID logo and Anup Rao ORCID logo
(University of Washington, USA)
Publisher's Version
Beating Brute Force for Compression Problems
Shuichi Hirahara ORCID logo, Rahul Ilango ORCID logo, and R. Ryan Williams ORCID logo
(National Institute of Informatics, Tokyo, Japan; Massachusetts Institute of Technology, USA)
Publisher's Version

4D

Optimization with Pattern-Avoiding Input
Benjamin Aram Berendsohn ORCID logo, László Kozma ORCID logo, and Michal Opler ORCID logo
(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 ORCID logo, Daniel Lokshtanov ORCID logo, Tomáš MasaříkORCID logo, Marcin Pilipczuk ORCID logo, Michał Pilipczuk ORCID logo, and Paweł Rzążewski ORCID logo
(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 ORCID logo, Ken-ichi Kawarabayashi ORCID logo, Stephan Kreutzer ORCID logo, and Sebastian Wiederrecht ORCID logo
(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 ORCID logo, Ken-ichi Kawarabayashi ORCID logo, and Stephan Kreutzer ORCID logo
(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 ORCID logo and Sebastian Wiederrecht ORCID logo
(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 ORCID logo, Manik Dhar ORCID logo, and Sivakanth Gopi ORCID logo
(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 ORCID logo, Manik Dhar ORCID logo, Sivakanth Gopi ORCID logo, and Zihan Zhang ORCID logo
(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 GuptaORCID logo
(University of California at Berkeley, USA)
Publisher's Version
Local Correction of Linear Functions over the Boolean Cube
Prashanth Amireddy ORCID logo, Amik Raj Behera ORCID logo, Manaswi Paraashar ORCID logo, Srikanth Srinivasan ORCID logo, and Madhu Sudan ORCID logo
(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. KothariORCID logo and Peter Manohar ORCID logo
(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 ORCID logo, Theo McKenzie ORCID logo, Sidhanth Mohanty ORCID logo, and Pedro Paredes ORCID logo
(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 ORCID logo, Erik Waingarten ORCID logo, and Tian Zhang ORCID logo
(Google Research, USA; University of Pennsylvania, USA)
Publisher's Version
Polylog-Competitive Deterministic Local Routing and Scheduling
Bernhard Haeupler ORCID logo, Shyamal Patel ORCID logo, Antti Roeyskoe ORCID logo, Cliff Stein ORCID logo, and Goran Zuzic ORCID logo
(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 ORCID logo, Asaf Petruschka ORCID logo, and Seth Pettie ORCID logo
(Weizmann Institute of Science, Israel; University of Michigan, USA)
Publisher's Version
Optimal Multi-pass Lower Bounds for MST in Dynamic Streams
Sepehr Assadi ORCID logo, Gillat Kol ORCID logo, and Zhijun Zhang ORCID logo
(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 ORCID logo, Christian Konrad ORCID logo, Kheeran K. Naidu ORCID logo, and Janani Sundaresan ORCID logo
(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 ORCID logo and Petteri Kaski ORCID logo
(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 ORCID logo
(New York University, USA)
Publisher's Version
Equality Cases of the Alexandrov–Fenchel Inequality Are Not in the Polynomial Hierarchy
Swee Hong ChanORCID logo and Igor PakORCID logo
(Rutgers University, USA; University of California at Los Angeles, USA)
Publisher's Version
Semigroup Algorithmic Problems in Metabelian Groups
Ruiwen Dong ORCID logo
(Saarland University, Saarbrücken, Germany)
Publisher's Version
The Complexity of Computing KKT Solutions of Quadratic Programs
John Fearnley ORCID logo, Paul W. Goldberg ORCID logo, Alexandros Hollender ORCID logo, and Rahul Savani ORCID logo
(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 ORCID logo, Joakim Blikstad ORCID logo, André Nusser ORCID logo, and Hanwen Zhang ORCID logo
(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 ORCID logo, Zhewei Wei ORCID logo, Ji-Rong Wen ORCID logo, and Mingji Yang ORCID logo
(Renmin University of China, China)
Publisher's Version
Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
Mina Dalirrooyfard ORCID logo, Surya Mathialagan ORCID logo, Virginia Vassilevska Williams ORCID logo, and Yinzhan Xu ORCID logo
(Morgan Stanley Research, Canada; Massachusetts Institute of Technology, USA)
Publisher's Version
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Amir Abboud ORCID logo, Nick Fischer ORCID logo, Zander Kelley ORCID logo, Shachar Lovett ORCID logo, and Raghu Meka ORCID logo
(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 ORCID logo and Manoj Gupta ORCID logo
(IIT Gandhinagar, India)
Publisher's Version
Almost Linear Size Edit Distance Sketch
Michal Koucký ORCID logo and Michael E. Saks ORCID logo
(Charles University, Prague, Czechia; Rutgers University, USA)
Publisher's Version

6B

Commitments from Quantum One-Wayness
Dakshita Khurana ORCID logo and Kabir Tomer ORCID logo
(University of Illinois at Urbana-Champaign, USA)
Publisher's Version
A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography
Alex LombardiORCID logo, Fermi Ma ORCID logo, and John Wright ORCID logo
(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 ORCID logo and William Slofstra ORCID logo
(University of Waterloo, Canada)
Publisher's Version
How to Use Quantum Indistinguishability Obfuscation
Andrea ColadangeloORCID logo and Sam Gunn ORCID logo
(University of Washington, USA; University of California at Berkeley, USA)
Publisher's Version
Quantum State Obfuscation from Classical Oracles
James Bartusek ORCID logo, Zvika Brakerski ORCID logo, and Vinod VaikuntanathanORCID logo
(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 ORCID logo, Khashayar Barooti ORCID logo, Alexandru Gheorghiu ORCID logo, and Marc-Olivier Renou ORCID logo
(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 ORCID logo, Huan Li ORCID logo, Shivam Nadimpalli ORCID logo, and Rocco A. Servedio ORCID logo
(University of Pennsylvania, USA; Columbia University, USA)
Publisher's Version
Optimal Non-adaptive Tolerant Junta Testing via Local Estimators
Shivam Nadimpalli ORCID logo and Shyamal Patel ORCID logo
(Columbia University, USA)
Publisher's Version
Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
Xi ChenORCID logo, Yumou Fei ORCID logo, and Shyamal Patel ORCID logo
(Columbia University, USA; Peking University, China)
Publisher's Version
On the Power of Interactive Proofs for Learning
Tom Gur ORCID logo, Mohammad Mahdi Jahanara ORCID logo, Mohammad Mahdi Khodabandeh ORCID logo, Ninad Rajgopal ORCID logo, Bahar Salamatian ORCID logo, and Igor Shinkar ORCID logo
(University of Cambridge, United Kingdom; Simon Fraser University, Canada; Qualcomm, Canada)
Publisher's Version
Complexity-Theoretic Implications of Multicalibration
Sílvia Casacuberta ORCID logo, Cynthia Dwork ORCID logo, and Salil Vadhan ORCID logo
(University of Oxford, United Kingdom; Harvard University, USA)
Publisher's Version

6D

Local Geometry of NAE-SAT Solutions in the Condensation Regime
Allan Sly ORCID logo and Youngtak Sohn ORCID logo
(Princeton University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version Info
Trickle-Down in Localization Schemes and Applications
Nima Anari ORCID logo, Frederic Koehler ORCID logo, and Thuy-Duong Vuong ORCID logo
(Stanford University, USA; University of Chicago, USA)
Publisher's Version
Optimal Embedding Dimension for Sparse Subspace Embeddings
Shabarish Chenakkod ORCID logo, Michał Dereziński ORCID logo, Xiaoyu Dong ORCID logo, and Mark Rudelson ORCID logo
(University of Michigan, USA)
Publisher's Version
Solving Dense Linear Systems Faster Than via Preconditioning
Michał Dereziński ORCID logo and Jiaming Yang ORCID logo
(University of Michigan, USA)
Publisher's Version
Improving the Bit Complexity of Communication for Distributed Convex Optimization
Mehrdad Ghadiri ORCID logo, Yin Tat Lee ORCID logo, Swati Padmanabhan ORCID logo, William Swartworth ORCID logo, David P. Woodruff ORCID logo, and Guanghao Ye ORCID logo
(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 ORCID logo
(Stanford University, USA)
Publisher's Version
Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval
William Kuszmaul ORCID logo and Stefan Walzer ORCID logo
(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 ORCID logo, Rasmus Kyng ORCID logo, Yang P. Liu ORCID logo, Simon Meierhans ORCID logo, and Maximilian Probst Gutenberg ORCID logo
(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 ORCID logo, Simon Meierhans ORCID logo, and Maximilian Probst Gutenberg ORCID logo
(ETH Zurich, Switzerland)
Publisher's Version
Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case Time
Mohsen Ghaffari ORCID logo and Christoph Grunau ORCID logo
(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 ORCID logo and S. Matthew Weinberg ORCID logo
(Princeton University, USA)
Publisher's Version
PPAD-Membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization
Aris Filos-Ratsikas ORCID logo, Kristoffer Arnsfelt Hansen ORCID logo, Kasper Høgh ORCID logo, and Alexandros Hollender ORCID logo
(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 ORCID logo, Constantinos Daskalakis ORCID logo, Maxwell FishelsonORCID logo, and Noah GolowichORCID logo
(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 ORCID logo and Aviad Rubinstein ORCID logo
(Columbia University, USA; Stanford University, USA)
Publisher's Version
Fair Division via Quantile Shares
Yakov Babichenko ORCID logo, Michal Feldman ORCID logo, Ron Holzman ORCID logo, and Vishnu V. Narayan ORCID logo
(Technion, Israel; Tel Aviv University, Israel)
Publisher's Version
Prophet Inequalities with Cancellation Costs
Farbod Ekbatani ORCID logo, Rad Niazadeh ORCID logo, Pranav Nuti ORCID logo, and Jan Vondrák ORCID logo
(University of Chicago, USA; Stanford University, USA)
Publisher's Version

7C

Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
Nicholas Harvey ORCID logo and Arvin Sahami ORCID logo
(University of British Columbia, Canada)
Publisher's Version
Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)
James Cook ORCID logo and Ian MertzORCID logo
(Unaffiliated, Canada; University of Warwick, United Kingdom)
Publisher's Version
Locality Bounds for Sampling Hamming Slices
Daniel M. KaneORCID logo, Anthony Ostuni ORCID logo, and Kewen Wu ORCID logo
(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 ORCID logo, Lianna Hambardzumyan ORCID logo, Nathaniel Harms ORCID logo, and Pooya Hatami ORCID logo
(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 ORCID logo, Shachar Lovett ORCID logo, and Raghu Meka ORCID logo
(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 ORCID logo, Raz Firanko ORCID logo, and Rahul Jain ORCID logo
(Centre for Quantum Technologies, Singapore; Technion, Israel; National University of Singapore, Singapore)
Publisher's Version
Local Minima in Quantum Systems
Chi-Fang Chen ORCID logo, Hsin-Yuan HuangORCID logo, John Preskill ORCID logo, and Leo Zhou ORCID logo
(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 ORCID logo, Jerry Li ORCID logo, and Allen Liu ORCID logo
(Harvard University, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
Learning Shallow Quantum Circuits
Hsin-Yuan HuangORCID logo, Yunchao Liu ORCID logo, Michael Broughton ORCID logo, Isaac Kim ORCID logo, Anurag Anshu ORCID logo, Zeph Landau ORCID logo, and Jarrod R. McClean ORCID logo
(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 ORCID logo, Vishnu Iyer ORCID logo, William Kretschmer ORCID logo, and Daniel Liang ORCID logo
(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 ChenORCID logo, Yuhao Li ORCID logo, and Mihalis Yannakakis ORCID logo
(Columbia University, USA)
Publisher's Version
Self-Improvement for Circuit-Analysis Problems
R. Ryan Williams ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication
Benjamin Rossman ORCID logo
(Duke University, USA)
Publisher's Version
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
Tuomas Hakoniemi ORCID logo, Nutan Limaye ORCID logo, and Iddo Tzameret ORCID logo
(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 ORCID logo, Stefan Grosser ORCID logo, Toniann Pitassi ORCID logo, and Robert Robere ORCID logo
(Memorial University of Newfoundland, Canada; McGill University, Canada; Columbia University, USA)
Publisher's Version

8B

Product Mixing in Compact Lie Groups
David Ellis ORCID logo, Guy Kindler ORCID logo, Noam Lifshitz ORCID logo, and Dor Minzer ORCID logo
(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 ORCID logo, Subhash Khot ORCID logo, and Dor Minzer ORCID logo
(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 ORCID logo and Naoto Ohsaka ORCID logo
(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 ORCID logo and Tali Kaufman ORCID logo
(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 ORCID logo, Venkatesan Guruswami ORCID logo, and Ray LiORCID logo
(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 ORCID logo, Allen Liu ORCID logo, Ankur Moitra ORCID logo, and Ewin Tang ORCID logo
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)
Publisher's Version
An Efficient Quantum Parallel Repetition Theorem and Applications
John BostanciORCID logo, Luowen Qian ORCID logo, Nicholas Spooner ORCID logo, and Henry YuenORCID logo
(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 ORCID logo, Makrand Sinha ORCID logo, Avishay Tal ORCID logo, and Kewen Wu ORCID logo
(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 ORCID logo, Natalie Parham ORCID logo, Francisca Vasconcelos ORCID logo, and Henry YuenORCID logo
(Columbia University, USA; University of California at Berkeley, USA)
Publisher's Version
Approaching the Quantum Singleton Bound with Approximate Error Correction
Thiago Bergamaschi ORCID logo, Louis Golowich ORCID logo, and Sam Gunn ORCID logo
(University of California at Berkeley, USA)
Publisher's Version

8D

Counting Small Induced Subgraphs with Edge-Monotone Properties
Simon Döring ORCID logo, Dániel Marx ORCID logo, and Philip Wellnitz ORCID logo
(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 MakarychevORCID logo, Naren Sarayu Manoj ORCID logo, and Max OvsiankinORCID logo
(Toyota Technological Institute, Chicago, USA)
Publisher's Version
Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic Rankwidth
Tuukka KorhonenORCID logo and Marek Sokołowski ORCID logo
(University of Bergen, Norway; University of Warsaw, Poland)
Publisher's Version
Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
Jan Dreier ORCID logo, Nikolas Mählmann ORCID logo, and Szymon Toruńczyk ORCID logo
(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 DadushORCID logo, Zhuan Khye KohORCID logo, Bento NaturaORCID logo, Neil OlverORCID logo, and László A. VéghORCID logo
(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 JinORCID logo and Yinzhan Xu ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
Relaxed Local Correctability from Local Testing
Vinayak M. Kumar ORCID logo and Geoffrey Mon ORCID logo
(University of Texas at Austin, USA)
Publisher's Version

10A

On Optimal Coreset Construction for Euclidean (k,z)-Clustering
Lingxiao Huang ORCID logo, Jian Li ORCID logo, and Xuan Wu ORCID logo
(Nanjing University, China; Tsinghua University, China)
Publisher's Version
Understanding the Cluster Linear Program for Correlation Clustering
Nairen CaoORCID logo, Vincent Cohen-Addad ORCID logo, Euiwoong Lee ORCID logo, Shi LiORCID logo, Alantha Newman ORCID logo, and Lukas Vogl ORCID logo
(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 ORCID logo, David Rasmussen Lolck ORCID logo, Marcin Pilipczuk ORCID logo, Mikkel Thorup ORCID logo, Shuyi Yan ORCID logo, and Hanwen Zhang ORCID logo
(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 ORCID logo and Will Ma ORCID logo
(Columbia University, USA)
Publisher's Version Info
Prize-Collecting Steiner Tree: A 1.79 Approximation
Ali Ahmadi ORCID logo, Iman Gholami ORCID logo, MohammadTaghi Hajiaghayi ORCID logo, Peyman Jabbarzade ORCID logo, and Mohammad Mahdavi ORCID logo
(University of Maryland, USA)
Publisher's Version

10B

Reconfiguration of Basis Pairs in Regular Matroids
Kristóf Bérczi ORCID logo, Bence Mátravölgyi ORCID logo, and Tamás Schwarcz ORCID logo
(University of Eötvös Loránd, Hungary; ETH Zurich, Switzerland)
Publisher's Version
Sparsifying Generalized Linear Models
Arun Jambulapati ORCID logo, James R. Lee ORCID logo, Yang P. Liu ORCID logo, and Aaron Sidford ORCID logo
(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 ORCID logo, Wesley Pegden ORCID logo, and Jamie Tucker-Foltz ORCID logo
(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 ORCID logo, Chihao Zhang ORCID logo, and Zihan Zhang ORCID logo
(Shanghai Jiao Tong University, China; SOKENDAI, Japan)
Publisher's Version
Hypergraph Unreliability in Quasi-Polynomial Time
Ruoxu Cen ORCID logo, Jason Li ORCID logo, and Debmalya PanigrahiORCID logo
(Duke University, USA; Carnegie Mellon University, USA)
Publisher's Version

10C

Memory Checking Requires Logarithmic Overhead
Elette Boyle ORCID logo, Ilan Komargodski ORCID logo, and Neekon Vafa ORCID logo
(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 ORCID logo, Jack O'Connor ORCID logo, and Nicholas Spooner ORCID logo
(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 ORCID logo and Mikito Nanashima ORCID logo
(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 ORCID logo, Tyler Besselman ORCID logo, Siyao Guo ORCID logo, Zhiye Xie ORCID logo, and Yuping Ye ORCID logo
(NYU Shanghai, China; East China Normal University, China)
Publisher's Version
SNARGs under LWE via Propositional Proofs
Zhengzhong Jin ORCID logo, Yael KalaiORCID logo, Alex LombardiORCID logo, and Vinod VaikuntanathanORCID logo
(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 ORCID logo, Jakob Nogler ORCID logo, and Philip Wellnitz ORCID logo
(MPI-INF, Germany; Saarland Informatics Campus, Saarbrücken, Germany; ETH Zurich, Switzerland)
Publisher's Version
Local Borsuk-Ulam, Stability, and Replicability
Zachary ChaseORCID logo, Bogdan Chornomaz ORCID logo, Shay MoranORCID logo, and Amir Yehudayoff ORCID logo
(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 ORCID logo, Sumegha Garg ORCID logo, Qian Li ORCID logo, Shuo Wang ORCID logo, David P. Woodruff ORCID logo, and Jiapeng Zhang ORCID logo
(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 ORCID logo and Cameron Seth ORCID logo
(University of Waterloo, Canada)
Publisher's Version
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
John Kallaugher ORCID logo, Ojas Parekh ORCID logo, and Nadezhda Voronova ORCID logo
(Sandia National Laboratories, USA; Boston University, USA)
Publisher's Version

11A

Proof of the Density Threshold Conjecture for Pinwheel Scheduling
Akitoshi Kawamura ORCID logo
(Kyoto University, Kyoto, Japan)
Publisher's Version
Constrained Submodular Maximization via New Bounds for DR-Submodular Functions
Niv Buchbinder ORCID logo and Moran Feldman ORCID logo
(Tel Aviv University, Israel; University of Haifa, Israel)
Publisher's Version
Optimal Online Discrepancy Minimization
Janardhan Kulkarni ORCID logo, Victor Reis ORCID logo, and Thomas Rothvoss ORCID logo
(Microsoft Research, USA; Institute for Advanced Study, Princeton, USA; University of Washington, USA)
Publisher's Version
Supermodular Approximation of Norms and Applications
Thomas Kesselheim ORCID logo, Marco Molinaro ORCID logo, and Sahil Singla ORCID logo
(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 ORCID logo, Nathan Klein ORCID logo, and Rico Zenklusen ORCID logo
(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 ORCID logo, Daniel AmirORCID logo, Nitika Saran ORCID logo, Robert KleinbergORCID logo, Vishal ShrivastavORCID logo, and Hakim WeatherspoonORCID logo
(Cornell University, USA; Purdue University, USA)
Publisher's Version
Lenzen’s Distributed Routing Generalized: A Full Characterization of Constant-Time Routability
Mohsen Ghaffari ORCID logo and Brandon Wang ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping
Mohsen Ghaffari ORCID logo and Christoph Grunau ORCID logo
(Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland)
Publisher's Version
No Distributed Quantum Advantage for Approximate Graph Coloring
Xavier Coiteux-Roy ORCID logo, Francesco d'AmoreORCID logo, Rishikesh Gajjala ORCID logo, Fabian Kuhn ORCID logo, François Le Gall ORCID logo, Henrik Lievonen ORCID logo, Augusto ModaneseORCID logo, Marc-Olivier Renou ORCID logo, Gustav Schmid ORCID logo, and Jukka Suomela ORCID logo
(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 ORCID logo, Praneeth Kacham ORCID logo, Vahab Mirrokni ORCID logo, David P. Woodruff ORCID logo, and Peilin Zhong ORCID logo
(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 ORCID logo, Aaron Potechin ORCID logo, and Jeff Xu ORCID logo
(Carnegie Mellon University, USA; University of Chicago, USA)
Publisher's Version
Semidefinite Programming and Linear Equations vs. Homomorphism Problems
Lorenzo Ciardo ORCID logo and Stanislav Živný ORCID logo
(University of Oxford, United Kingdom)
Publisher's Version
How Random CSPs Fool Hierarchies
Siu On Chan ORCID logo, Hiu Tsun Ng ORCID logo, and Sijin Peng ORCID logo
(Unaffiliated, Hong Kong, China; Chinese University of Hong Kong, China; Tsinghua University, China)
Publisher's Version
Swap Cosystolic Expansion
Yotam Dikstein ORCID logo and Irit Dinur ORCID logo
(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 ORCID logo and Irit Dinur ORCID logo
(Institute for Advanced Study, Princeton, USA; Weizmann Institute of Science, Israel)
Publisher's Version
Characterizing Direct Product Testing via Coboundary Expansion
Mitali BafnaORCID logo and Dor Minzer ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version

11D

Symmetric Exponential Time Requires Near-Maximum Circuit Size
Lijie Chen ORCID logo, Shuichi Hirahara ORCID logo, and Hanlin RenORCID logo
(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 ORCID logo
(National University of Singapore, Singapore)
Publisher's Version
Random (log 𝑛)-CNF Are Hard for Cutting Planes (Again)
Dmitry Sokolov ORCID logo
(EPFL, Lausanne, Switzerland)
Publisher's Version
Hardness Condensation by Restriction
Mika Göös ORCID logo, Ilan Newman ORCID logo, Artur Riazanov ORCID logo, and Dmitry Sokolov ORCID logo
(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 ORCID logo and Jad Silbak ORCID logo
(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 ORCID logo, Edward Pyne ORCID logo, and Roei Tell ORCID logo
(Ben-Gurion University of the Negev, Israel; Massachusetts Institute of Technology, USA; University of Toronto, Canada)
Publisher's Version

proc time: 33.87