STOC 2024
56th Annual ACM Symposium on Theory of Computing (STOC 2024)

Title Page

Article: stoc24foreword-fm000-p doi:

Welcome from the Program Chair

Article: stoc24foreword-fm001-p doi:

STOC 2024 Conference Organization

Article: stoc24foreword-fm002-p doi:

Sponsors

Article: stoc24foreword-fm003-p doi:

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

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

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

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

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

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

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

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

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

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

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 o