default search action
56th STOC 2024: Vancouver, BC, Canada
- Bojan Mohar, Igor Shinkar, Ryan O'Donnell:
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024. ACM 2024
Keynotes
- Tim Roughgarden
:
The Computer in the Sky (Keynote). 1 - Michal Feldman
Algorithmic Contract Design (Keynote). 2
1A (Best Papers)
- Jeremy T. Fineman
Single-Source Shortest Paths with Negative Real Weights in Õ(mn8/9) Time. 3-14 - Dor Minzer
Near Optimal Alphabet-Soundness Tradeoff PCPs. 15-23 - Venkatesan Guruswami
Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis. 24-35
2A
- Joakim Blikstad
Online Edge Coloring Is (Nearly) as Easy as Offline. 36-46 - Lorenzo Beretta
Approximate Earth Mover's Distance in Truly-Subquadratic Time. 47-58 - Sayan Bhattacharya
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs. 59-70 - Bernhard Haeupler
Low-Step Multi-commodity Flow Emulators. 71-82 - Julia Chuzhoy
Maximum Bipartite Matching in n2+o(1) Time via a Combinatorial Algorithm. 83-94
2B
- Rafael Oliveira
Strong Algebras and Radical Sylvester-Gallai Configurations. 95-105 - Vikraman Arvind
Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time. 106-117 - Bireswar Das
The Minimal Faithful Permutation Degree of Groups without Abelian Normal Subgroups. 118-129 - C. S. Bhargav
Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring. 130-140 - Hervé Fournier, Nutan Limaye
On the Power of Homogeneous Algebraic Formulas. 141-151
2C
- Ilias Diakonikolas
Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs. 152-159 - Adam Tauman Kalai
Calibrated Language Models Must Hallucinate. 160-171 - Hongjie Chen
Private Graphon Estimation via Sum-of-Squares. 172-182 - Noah Golowich
Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles. 183-193 - Spencer Compton
Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances. 194-200
2D
- Yang Cai
The Power of Two-Sided Recruitment in Two-Sided Markets. 201-212 - Yiding Feng
Strategic Budget Selection in a Competitive Autobidding World. 213-224 - Nicolò Cesa-Bianchi
The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations. 225-236 - Shahar Dobzinski
Bilateral Trade with Correlated Values. 237-246 - Martino Bernasconi
No-Regret Learning in Bilateral Trade via Global Budget Balance. 247-258
3A
- Karl Bringmann
Knapsack with Small Items in Near-Quadratic Time. 259-270 - Ce Jin
0-1 Knapsack in Nearly Quadratic Time. 271-282 - Lin Chen
A Nearly Quadratic-Time FPTAS for Knapsack. 283-294 - Xiao Mao
(1 - ε)-Approximation of Knapsack in Nearly Quadratic Time. 295-306 - Lin Chen
Approximating Partition in Near-Linear Time. 307-318 - Aditya Anand
Approximating Small Sparse Cuts. 319-330 - Ken-ichi Kawarabayashi
Better Coloring of 3-Colorable Graphs. 331-339
3B
- Ilias Diakonikolas
Testing Closeness of Multivariate Distributions via Ramsey Theory. 340-347 - Misha Ivkov
Semidefinite Programs Simulate Approximate Message Passing Robustly. 348-357 - Shuichi Hirahara
Planted Clique Conjectures Are Equivalent. 358-366 - Sidhanth Mohanty
Robust Recovery for Stochastic Block Models, Simplified and Generalized. 367-374 - Aditya Bhaskara
New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries. 375-386
3C
- Brent Waters
Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation. 387-398 - Brent Waters
A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors. 399-410 - Yuval Gelles
Optimal Load-Balanced Scalable Distributed Agreement. 411-422 - Thomas Debris-Alazard
Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs. 423-434 - Nir Bitansky
Batch Proofs Are Statistically Hiding. 435-443
3D
- Soheil Behnezhad
Approximating Maximum Matching Requires Almost Quadratic Time. 444-454 - Yannai A. Gonczarowski
Structural Complexities of Matching Mechanisms. 455-466 - Shahar Dobzinski
A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations. 467-478 - Shaddin Dughmi
Limitations of Stochastic Selection Problems with Pairwise Independent Priors. 479-490 - Andrés Cristi
Prophet Inequalities Require Only a Constant Number of Samples. 491-502
4A
- Jason Gaitonde
A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width. 503-514 - Pietro Caputo
Nonlinear Dynamics for the Ising Model. 515-526 - Frederic Koehler
Influences in Mixing Measures. 527-536 - Nima Anari
Parallel Sampling via Counting. 537-548 - Kiril Bangachev
On the Fourier Coefficients of High-Dimensional Random Geometric Graphs. 549-560
4B
- Sergey Bravyi
Classical Simulation of Peaked Shallow Quantum Circuits. 561-572 - Ashley Montanaro
Quantum and Classical Query Complexities of Functions of Matrices. 573-584 - Anurag Anshu
Circuit-to-Hamiltonian from Tensor Networks and Fault Tolerance. 585-595 - Paul Beame
Quantum Time-Space Tradeoffs for Matrix Problems. 596-607 - Saeed Mehraban
Quadratic Lower Bounds on the Approximate Stabilizer Rank: A Probabilistic Approach. 608-619
4C
- Yilei Chen
Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography. 620-629 - Guangxu Yang
Communication Lower Bounds for Collision Problems via Density Increment Arguments. 630-639 - Klim Efremenko
Lower Bounds for Regular Resolution over Parities. 640-651 - Siddharth Iyer
XOR Lemmas for Communication via Marginal Information. 652-658 - Shuichi Hirahara
Beating Brute Force for Compression Problems. 659-670
4D
- Benjamin Aram Berendsohn
Optimization with Pattern-Avoiding Input. 671-682 - Peter Gartland, Daniel Lokshtanov
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time. 683-691 - Maximilian Gorsky
Packing Even Directed Circuits Quarter-Integrally. 692-703 - Dario Giuliano Cavallaro
Edge-Disjoint Paths in Eulerian Digraphs. 704-715 - Archontia C. Giannopoulou
A Flat Wall Theorem for Matching Minors in Bipartite Graphs. 716-727
5A
- Joshua Brakensiek
Generalized GM-MDS: Polynomial Codes Are Higher Order MDS. 728-739 - Joshua Brakensiek
AG Codes Achieve List Decoding Capacity over Constant-Sized Fields. 740-751 - Meghal Gupta
Constant Query Local Decoding against Deletions Is Impossible. 752-763 - Prashanth Amireddy
Local Correction of Linear Functions over the Boolean Cube. 764-775 - Pravesh K. Kothari
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes. 776-787 - Jun-Ting Hsieh
Explicit Two-Sided Unique-Neighbor Expanders. 788-799
5B
- Rajesh Jayaram
Data-Dependent LSH for the Earth Mover's Distance. 800-811 - Bernhard Haeupler
Polylog-Competitive Deterministic Local Routing and Scheduling. 812-822 - Merav Parter
Connectivity Labeling and Routing with Multiple Vertex Failures. 823-834 - Sepehr Assadi
Optimal Multi-pass Lower Bounds for MST in Dynamic Streams. 835-846 - Sepehr Assadi
O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set. 847-858
5C
- Andreas Björklund
The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True. 859-870 - Kevin Pratt
A Stronger Connection between the Asymptotic Rank Conjecture and the Set Cover Conjecture. 871-874 - Swee Hong Chan
Equality Cases of the Alexandrov-Fenchel Inequality Are Not in the Polynomial Hierarchy. 875-883 - Ruiwen Dong
Semigroup Algorithmic Problems in Metabelian Groups. 884-891 - John Fearnley
The Complexity of Computing KKT Solutions of Quadratic Programs. 892-903 - Mikkel Abrahamsen
Minimum Star Partitions of Simple Polygons in Polynomial Time. 904-910
6A
- Hanzhi Wang
Revisiting Local Computation of PageRank: Simple and Optimal. 911-922 - Mina Dalirrooyfard
Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques. 923-934 - Amir Abboud
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. 935-943 - Dipan Dey
Nearly Optimal Fault Tolerant Distance Oracle. 944-955 - Michal Koucký
Almost Linear Size Edit Distance Sketch. 956-967
6B
- Dakshita Khurana
Commitments from Quantum One-Wayness. 968-978 - Alex Lombardi
A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography. 979-990 - Kieran Mastel
Two Prover Perfect Zero Knowledge for MIP. 991-1002 - Andrea Coladangelo
How to Use Quantum Indistinguishability Obfuscation. 1003-1008 - James Bartusek
Quantum State Obfuscation from Classical Oracles. 1009-1017 - Grzegorz Gluch
Nonlocality under Computational Assumptions. 1018-1026
6C
- Anindya De
Detecting Low-Degree Truncation. 1027-1038 - Shivam Nadimpalli
Optimal Non-adaptive Tolerant Junta Testing via Local Estimators. 1039-1050 - Xi Chen
Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries. 1051-1062 - Tom Gur
On the Power of Interactive Proofs for Learning. 1063-1070 - Sílvia Casacuberta
Complexity-Theoretic Implications of Multicalibration. 1071-1082
6D
- Allan Sly
Local Geometry of NAE-SAT Solutions in the Condensation Regime. 1083-1093 - Nima Anari
Trickle-Down in Localization Schemes and Applications. 1094-1105 - Shabarish Chenakkod
Optimal Embedding Dimension for Sparse Subspace Embeddings. 1106-1117 - Michal Derezinski
Solving Dense Linear Systems Faster Than via Preconditioning. 1118-1129 - Mehrdad Ghadiri
Improving the Bit Complexity of Communication for Distributed Convex Optimization. 1130-1140
7A
- Xiao Mao
Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time. 1141-1152 - William Kuszmaul
Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval. 1153-1164 - Li Chen
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow. 1165-1173 - Rasmus Kyng
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications. 1174-1183 - Mohsen Ghaffari
Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case Time. 1184-1191
7B
- Frederick V. Qiu
Settling the Communication Complexity of VCG-Based Mechanisms for All Approximation Guarantees. 1192-1203 - Aris Filos-Ratsikas
PPAD-Membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization. 1204-1215 - Yuval Dagan
From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces. 1216-1222 - Binghui Peng
Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria. 1223-1234 - Yakov Babichenko
Fair Division via Quantile Shares. 1235-1246 - Farbod Ekbatani
Prophet Inequalities with Cancellation Costs. 1247-1258
7C
- Nicholas Harvey
Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters. 1259-1267 - James Cook
Tree Evaluation Is in Space O(log n · log log n). 1268-1278 - Daniel M. Kane
Locality Bounds for Sampling Hamming Slices. 1279-1286 - Yuting Fang
No Complete Problem for Constant-Cost Randomized Communication. 1287-1298 - Zander Kelley
Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication. 1299-1310
7D
- Itai Arad
An Area Law for the Maximally-Mixed Ground State in Arbitrarily Degenerate Systems with Good AGSP. 1311-1322 - Chi-Fang Chen
Local Minima in Quantum Systems. 1323-1330 - Sitan Chen
An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography. 1331-1342 - Hsin-Yuan Huang
Learning Shallow Quantum Circuits. 1343-1351 - Sabee Grewal
Improved Stabilizer Estimation via Bell Difference Sampling. 1352-1363
8A
- Xi Chen
Computing a Fixed Point of Contraction Maps in Polynomial Queries. 1364-1373 - R. Ryan Williams
Self-Improvement for Circuit-Analysis Problems. 1374-1385 - Benjamin Rossman
Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication. 1386-1395 - Tuomas Hakoniemi
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers. 1396-1404 - Noah Fleming
Black-Box PPP Is Not Turing-Closed. 1405-1414
8B
- David Ellis
Product Mixing in Compact Lie Groups. 1415-1422 - Amey Bhangale
On Approximability of Satisfiable k-CSPs: IV. 1423-1434 - Shuichi Hirahara
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems. 1435-1445 - Uriya A. First
Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes. 1446-1457 - Omar Alrabiah
Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields. 1458-1469
8C
- Ainesh Bakshi
Learning Quantum Hamiltonians at Any Temperature in Polynomial Time. 1470-1477 - John Bostanci
An Efficient Quantum Parallel Repetition Theorem and Applications. 1478-1487 - Uma Girish
The Power of Adaptivity in Quantum Query Algorithms. 1488-1497 - Shivam Nadimpalli
On the Pauli Spectrum of QAC0. 1498-1506 - Thiago Bergamaschi
Approaching the Quantum Singleton Bound with Approximate Error Correction. 1507-1516
8D
- Simon Döring
Counting Small Induced Subgraphs with Edge-Monotone Properties. 1517-1525 - Yury Makarychev
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes. 1526-1537 - Tuukka Korhonen
Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic Rankwidth. 1538-1549 - Jan Dreier
Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes. 1550-1560 - Daniel Dadush
A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column. 1561-1572
9A (Best Student Papers)
- Ce Jin
Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More. 1573-1584 - Vinayak M. Kumar
Relaxed Local Correctability from Local Testing. 1585-1593
10A
- Lingxiao Huang
On Optimal Coreset Construction for Euclidean (k, z)-Clustering. 1594-1604 - Nairen Cao
Understanding the Cluster Linear Program for Correlation Clustering. 1605-1616 - Vincent Cohen-Addad
Combinatorial Correlation Clustering. 1617-1628 - Calum MacRury
Random-Order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals. 1629-1640 - Ali Ahmadi
Prize-Collecting Steiner Tree: A 1.79 Approximation. 1641-1652
10B
- Kristóf Bérczi
Reconfiguration of Basis Pairs in Regular Matroids. 1653-1664 - Arun Jambulapati
Sparsifying Generalized Linear Models. 1665-1675 - Sarah Cannon
Sampling Balanced Forests of Grids in Polynomial Time. 1676-1687 - Yulin Wang
Sampling Proper Colorings on Line Graphs Using (1+o(1))Δ Colors. 1688-1699 - Ruoxu Cen
Hypergraph Unreliability in Quasi-Polynomial Time. 1700-1711
10C
- Elette Boyle
Memory Checking Requires Logarithmic Overhead. 1712-1723 - Tom Gur
Perfect Zero-Knowledge PCPs for #P. 1724-1730 - Shuichi Hirahara
One-Way Functions and Zero Knowledge. 1731-1738 - Akshima
Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem. 1739-1749 - Zhengzhong Jin
SNARGs under LWE via Propositional Proofs. 1750-1757
10D
- Tomasz Kociumaka
On the Communication Complexity of Approximate Pattern Matching. 1758-1768 - Zachary Chase
Local Borsuk-Ulam, Stability, and Replicability. 1769-1780 - Mark Braverman
A New Information Complexity Measure for Multi-pass Streaming with Applications. 1781-1792 - Eric Blais
New Graph and Hypergraph Container Lemmas with Applications in Property Testing. 1793-1804 - John Kallaugher
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model. 1805-1815
11A
- Akitoshi Kawamura
Proof of the Density Threshold Conjecture for Pinwheel Scheduling. 1816-1819 - Niv Buchbinder
Constrained Submodular Maximization via New Bounds for DR-Submodular Functions. 1820-1831 - Janardhan Kulkarni
Optimal Online Discrepancy Minimization. 1832-1840 - Thomas Kesselheim
Supermodular Approximation of Norms and Applications. 1841-1852 - D. Ellis Hershkowitz
Ghost Value Augmentation for k-Edge-Connectivity. 1853-1864
11B
- Tegan Wilson
Breaking the VLB Barrier for Oblivious Reconfigurable Networks. 1865-1876 - Mohsen Ghaffari
Lenzen's Distributed Routing Generalized: A Full Characterization of Constant-Time Routability. 1877-1888 - Mohsen Ghaffari
Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping. 1889-1900 - Xavier Coiteux-Roy
No Distributed Quantum Advantage for Approximate Graph Coloring. 1901-1910 - Hossein Esfandiari
Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond. 1911-1922
11C
- Pravesh K. Kothari
Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs. 1923-1934 - Lorenzo Ciardo
Semidefinite Programming and Linear Equations vs. Homomorphism Problems. 1935-1943 - Siu On Chan
How Random CSPs Fool Hierarchies. 1944-1955 - Yotam Dikstein
Swap Cosystolic Expansion. 1956-1966 - Yotam Dikstein
Agreement Theorems for High Dimensional Expanders in the Low Acceptance Regime: The Role of Covers. 1967-1977 - Mitali Bafna
Characterizing Direct Product Testing via Coboundary Expansion. 1978-1989
11D
- Lijie Chen
Symmetric Exponential Time Requires Near-Maximum Circuit Size. 1990-1999 - Zeyong Li
Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform. 2000-2007 - Dmitry Sokolov
Random (log n)-CNF Are Hard for Cutting Planes (Again). 2008-2015 - Mika Göös
Hardness Condensation by Restriction. 2016-2027 - Ronen Shaltiel
Explicit Codes for Poly-Size Circuits and Functions That Are Hard to Sample on Low Entropy Distributions. 2028-2038 - Dean Doron
Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL. 2039-2049
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-27 21:14 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: