STOC 2024 – Proceedings

Frontmatter

Keynotes

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

Publisher's Version Article: stoc24main-key1-p doi:10.1145/3618260.3664271

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

Publisher's Version Article: stoc24main-key3-p doi:10.1145/3618260.3664273

1A (Best Papers)

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

Publisher's Version Article: stoc24main-p49-p doi:10.1145/3618260.3649614

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

Publisher's Version Article: stoc24main-p21-p doi:10.1145/3618260.3649606

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 Article: stoc24main-p1264-p doi:10.1145/3618260.3649771

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 Article: stoc24main-p891-p doi:10.1145/3618260.3649741

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 Article: stoc24main-p97-p doi:10.1145/3618260.3649629

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 Article: stoc24main-p175-p doi:10.1145/3618260.3649648

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 Article: stoc24main-p429-p doi:10.1145/3618260.3649689

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 Article: stoc24main-p726-p doi:10.1145/3618260.3649725

2B

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

Publisher's Version Article: stoc24main-p58-p doi:10.1145/3618260.3649617

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 Article: stoc24main-p448-p doi:10.1145/3618260.3649693

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

Publisher's Version Article: stoc24main-p156-p doi:10.1145/3618260.3649641

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 Article: stoc24main-p922-p doi:10.1145/3618260.3649743

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 Article: stoc24main-p1106-p doi:10.1145/3618260.3649760

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 Article: stoc24main-p1369-p doi:10.1145/3618260.3649776

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

Publisher's Version Article: stoc24main-p1400-p doi:10.1145/3618260.3649777

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 Article: stoc24main-p159-p doi:10.1145/3618260.3649643

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 Article: stoc24main-p579-p doi:10.1145/3618260.3649710

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

Publisher's Version Article: stoc24main-p1045-p doi:10.1145/3618260.3649754

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 Article: stoc24main-p319-p doi:10.1145/3618260.3649669

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 Article: stoc24main-p425-p doi:10.1145/3618260.3649688

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 Article: stoc24main-p255-p doi:10.1145/3618260.3649658

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

Publisher's Version Article: stoc24main-p256-p doi:10.1145/3618260.3649659

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 Article: stoc24main-p212-p doi:10.1145/3618260.3649653

3A

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

Publisher's Version Article: stoc24main-p664-p doi:10.1145/3618260.3649719

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

Publisher's Version Article: stoc24main-p59-p doi:10.1145/3618260.3649618

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

Publisher's Version Article: stoc24main-p797-p doi:10.1145/3618260.3649730

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

Publisher's Version Article: stoc24main-p365-p doi:10.1145/3618260.3649677

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

Publisher's Version Article: stoc24main-p758-p doi:10.1145/3618260.3649727

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

Publisher's Version Article: stoc24main-p972-p doi:10.1145/3618260.3649747

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 Article: stoc24main-p1255-p doi:10.1145/3618260.3649768

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 Article: stoc24main-p244-p doi:10.1145/3618260.3649657

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

Publisher's Version Article: stoc24main-p602-p doi:10.1145/3618260.3649713

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 Article: stoc24main-p1010-p doi:10.1145/3618260.3649751

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 Article: stoc24main-p1111-p doi:10.1145/3618260.3649761

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 Article: stoc24main-p1150-p doi:10.1145/3618260.3649765

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 Article: stoc24main-p330-p doi:10.1145/3618260.3649671

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 Article: stoc24main-p401-p doi:10.1145/3618260.3649683

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

Publisher's Version Article: stoc24main-p827-p doi:10.1145/3618260.3649736

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 Article: stoc24main-p1194-p doi:10.1145/3618260.3649766

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 Article: stoc24main-p1365-p doi:10.1145/3618260.3649775

3D

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

Publisher's Version Article: stoc24main-p1563-p doi:10.1145/3618260.3649785

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

Publisher's Version Article: stoc24main-p828-p doi:10.1145/3618260.3649737

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 Article: stoc24main-p872-p doi:10.1145/3618260.3649740

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 Article: stoc24main-p655-p doi:10.1145/3618260.3649718

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 Article: stoc24main-p1317-p doi:10.1145/3618260.3649773

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 Article: stoc24main-p346-p doi:10.1145/3618260.3649674

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

Publisher's Version Article: stoc24main-p1091-p doi:10.1145/3618260.3649759

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 Article: stoc24main-p798-p doi:10.1145/3618260.3649731

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

Publisher's Version Article: stoc24main-p931-p doi:10.1145/3618260.3649744

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

Publisher's Version Article: stoc24main-p356-p doi:10.1145/3618260.3649676

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 Article: stoc24main-p141-p doi:10.1145/3618260.3649638

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 Article: stoc24main-p296-p doi:10.1145/3618260.3649665

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 Article: stoc24main-p434-p doi:10.1145/3618260.3649690

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 Article: stoc24main-p546-p doi:10.1145/3618260.3649700

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 Article: stoc24main-p819-p doi:10.1145/3618260.3649733

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 Article: stoc24main-p7-p doi:10.1145/3618260.3649602

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

Publisher's Version Article: stoc24main-p25-p doi:10.1145/3618260.3649607

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 Article: stoc24main-p197-p doi:10.1145/3618260.3649652

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

Publisher's Version Article: stoc24main-p750-p doi:10.1145/3618260.3649726

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 Article: stoc24main-p1425-p doi:10.1145/3618260.3649778

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 Article: stoc24main-p118-p doi:10.1145/3618260.3649631

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 Article: stoc24main-p145-p doi:10.1145/3618260.3649791

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 Article: stoc24main-p391-p doi:10.1145/3618260.3649682

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 Article: stoc24main-p1070-p doi:10.1145/3618260.3649758

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 Article: stoc24main-p1351-p doi:10.1145/3618260.3649774

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 Article: stoc24main-p135-p doi:10.1145/3618260.3649637

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 Article: stoc24main-p193-p doi:10.1145/3618260.3649651

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

Publisher's Version Article: stoc24main-p227-p doi:10.1145/3618260.3649655

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 Article: stoc24main-p954-p doi:10.1145/3618260.3649746

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 Article: stoc24main-p155-p doi:10.1145/3618260.3649640

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 Article: stoc24main-p566-p doi:10.1145/3618260.3649705

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 Article: stoc24main-p310-p doi:10.1145/3618260.3649666

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 Article: stoc24main-p370-p doi:10.1145/3618260.3649678

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 Article: stoc24main-p785-p doi:10.1145/3618260.3649729

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 Article: stoc24main-p1046-p doi:10.1145/3618260.3649755

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 Article: stoc24main-p1123-p doi:10.1145/3618260.3649763

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 Article: stoc24main-p230-p doi:10.1145/3618260.3649656

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

Publisher's Version Article: stoc24main-p64-p doi:10.1145/3618260.3649620

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 Article: stoc24main-p167-p doi:10.1145/3618260.3649646

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

Publisher's Version Article: stoc24main-p30-p doi:10.1145/3618260.3649609

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 Article: stoc24main-p170-p doi:10.1145/3618260.3649647

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 Article: stoc24main-p1052-p doi:10.1145/3618260.3649756

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 Article: stoc24main-p276-p doi:10.1145/3618260.3649661

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 Article: stoc24main-p288-p doi:10.1145/3618260.3649663

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 Article: stoc24main-p481-p doi:10.1145/3618260.3649696

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

Publisher's Version Article: stoc24main-p517-p doi:10.1145/3618260.3649697

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

Publisher's Version Article: stoc24main-p1527-p doi:10.1145/3618260.3649783

6B

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

Publisher's Version Article: stoc24main-p219-p doi:10.1145/3618260.3649654

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 Article: stoc24main-p179-p doi:10.1145/3618260.3649650

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

Publisher's Version Article: stoc24main-p555-p doi:10.1145/3618260.3649702

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

Publisher's Version Article: stoc24main-p1449-p doi:10.1145/3618260.3649779

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 Article: stoc24main-p345-p doi:10.1145/3618260.3649673

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 Article: stoc24main-p1004-p doi:10.1145/3618260.3649750

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 Article: stoc24main-p129-p doi:10.1145/3618260.3649633

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

Publisher's Version Article: stoc24main-p420-p doi:10.1145/3618260.3649687

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 Article: stoc24main-p650-p doi:10.1145/3618260.3649717

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 Article: stoc24main-p1542-p doi:10.1145/3618260.3649784

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

Publisher's Version Article: stoc24main-p982-p doi:10.1145/3618260.3649748

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 Article: stoc24main-p1497-p doi:10.1145/3618260.3649781

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 Article: stoc24main-p76-p doi:10.1145/3618260.3649622

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

Publisher's Version Article: stoc24main-p1115-p doi:10.1145/3618260.3649762

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

Publisher's Version Article: stoc24main-p464-p doi:10.1145/3618260.3649694

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 Article: stoc24main-p1603-p doi:10.1145/3618260.3649787

7A

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

Publisher's Version Article: stoc24main-p466-p doi:10.1145/3618260.3649695

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

Publisher's Version Article: stoc24main-p177-p doi:10.1145/3618260.3649649

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 Article: stoc24main-p949-p doi:10.1145/3618260.3649745

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 Article: stoc24main-p1197-p doi:10.1145/3618260.3649767

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 Article: stoc24main-p1517-p doi:10.1145/3618260.3649782

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 Article: stoc24main-p568-p doi:10.1145/3618260.3649706

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 Article: stoc24main-p166-p doi:10.1145/3618260.3649645

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 Article: stoc24main-p389-p doi:10.1145/3618260.3649681

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

Publisher's Version Article: stoc24main-p438-p doi:10.1145/3618260.3649691

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

Publisher's Version Article: stoc24main-p764-p doi:10.1145/3618260.3649728

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 Article: stoc24main-p1593-p doi:10.1145/3618260.3649786

7C

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

Publisher's Version Article: stoc24main-p157-p doi:10.1145/3618260.3649642

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

Publisher's Version Article: stoc24main-p294-p doi:10.1145/3618260.3649664

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 Article: stoc24main-p320-p doi:10.1145/3618260.3649670

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 Article: stoc24main-p637-p doi:10.1145/3618260.3649716

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 Article: stoc24main-p701-p doi:10.1145/3618260.3649721

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 Article: stoc24main-p47-p doi:10.1145/3618260.3649612

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 Article: stoc24main-p355-p doi:10.1145/3618260.3649675

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 Article: stoc24main-p558-p doi:10.1145/3618260.3649704

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 Article: stoc24main-p715-p doi:10.1145/3618260.3649722

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 Article: stoc24main-p845-p doi:10.1145/3618260.3649738

8A

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

Publisher's Version Article: stoc24main-p78-p doi:10.1145/3618260.3649623

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

Publisher's Version Article: stoc24main-p718-p doi:10.1145/3618260.3649723

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

Publisher's Version Article: stoc24main-p94-p doi:10.1145/3618260.3649628

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 Article: stoc24main-p57-p doi:10.1145/3618260.3649616

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 Article: stoc24main-p1259-p doi:10.1145/3618260.3649769

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 Article: stoc24main-p91-p doi:10.1145/3618260.3649626

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 Article: stoc24main-p34-p doi:10.1145/3618260.3649610

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 Article: stoc24main-p311-p doi:10.1145/3618260.3649667

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 Article: stoc24main-p83-p doi:10.1145/3618260.3649625

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 Article: stoc24main-p130-p doi:10.1145/3618260.3649634

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 Article: stoc24main-p62-p doi:10.1145/3618260.3649619

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 Article: stoc24main-p10-p doi:10.1145/3618260.3649603

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 Article: stoc24main-p66-p doi:10.1145/3618260.3649621

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 Article: stoc24main-p287-p doi:10.1145/3618260.3649662

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 Article: stoc24main-p387-p doi:10.1145/3618260.3649680

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 Article: stoc24main-p162-p doi:10.1145/3618260.3649644

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 Article: stoc24main-p440-p doi:10.1145/3618260.3649692

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 Article: stoc24main-p802-p doi:10.1145/3618260.3649732

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 Article: stoc24main-p867-p doi:10.1145/3618260.3649739

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 Article: stoc24main-p1131-p doi:10.1145/3618260.3649764

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 Article: stoc24main-p15-p doi:10.1145/3618260.3649605

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

Publisher's Version Article: stoc24main-p43-p doi:10.1145/3618260.3649611

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 Article: stoc24main-p570-p doi:10.1145/3618260.3649707

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 Article: stoc24main-p996-p doi:10.1145/3618260.3649749

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 Article: stoc24main-p600-p doi:10.1145/3618260.3649712

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 Article: stoc24main-p1612-p doi:10.1145/3618260.3649788

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 Article: stoc24main-p1622-p doi:10.1145/3618260.3649789

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 Article: stoc24main-p269-p doi:10.1145/3618260.3649660

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 Article: stoc24main-p402-p doi:10.1145/3618260.3649684

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 Article: stoc24main-p525-p doi:10.1145/3618260.3649699

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 Article: stoc24main-p719-p doi:10.1145/3618260.3649724

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

Publisher's Version Article: stoc24main-p1042-p doi:10.1145/3618260.3649753

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 Article: stoc24main-p413-p doi:10.1145/3618260.3649686

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 Article: stoc24main-p520-p doi:10.1145/3618260.3649698

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 Article: stoc24main-p553-p doi:10.1145/3618260.3649701

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 Article: stoc24main-p1023-p doi:10.1145/3618260.3649752

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 Article: stoc24main-p1260-p doi:10.1145/3618260.3649770

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 Article: stoc24main-p13-p doi:10.1145/3618260.3649604

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 Article: stoc24main-p119-p doi:10.1145/3618260.3649632

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 Article: stoc24main-p341-p doi:10.1145/3618260.3649672

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

Publisher's Version Article: stoc24main-p576-p doi:10.1145/3618260.3649708

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 Article: stoc24main-p577-p doi:10.1145/3618260.3649709

11A

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

Publisher's Version Article: stoc24main-p1056-p doi:10.1145/3618260.3649757

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 Article: stoc24main-p113-p doi:10.1145/3618260.3649630

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 Article: stoc24main-p695-p doi:10.1145/3618260.3649720

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 Article: stoc24main-p820-p doi:10.1145/3618260.3649734

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 Article: stoc24main-p621-p doi:10.1145/3618260.3649715

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 Article: stoc24main-p29-p doi:10.1145/3618260.3649608

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 Article: stoc24main-p92-p doi:10.1145/3618260.3649627

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 Article: stoc24main-p315-p doi:10.1145/3618260.3649668

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 Article: stoc24main-p383-p doi:10.1145/3618260.3649679

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 Article: stoc24main-p901-p doi:10.1145/3618260.3649742

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 Article: stoc24main-p556-p doi:10.1145/3618260.3649703

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

Publisher's Version Article: stoc24main-p131-p doi:10.1145/3618260.3649635

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 Article: stoc24main-p48-p doi:10.1145/3618260.3649613

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

Publisher's Version Article: stoc24main-p1471-p doi:10.1145/3618260.3649780

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 Article: stoc24main-p409-p doi:10.1145/3618260.3649685

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

Publisher's Version Article: stoc24main-p610-p doi:10.1145/3618260.3649714

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 Article: stoc24main-p79-p doi:10.1145/3618260.3649624

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

Publisher's Version Article: stoc24main-p52-p doi:10.1145/3618260.3649615

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

Publisher's Version Article: stoc24main-p133-p doi:10.1145/3618260.3649636

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

Publisher's Version Article: stoc24main-p586-p doi:10.1145/3618260.3649711

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 Article: stoc24main-p823-p doi:10.1145/3618260.3649735

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 Article: stoc24main-p1312-p doi:10.1145/3618260.3649772

proc time: 0.54