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

55th Annual ACM Symposium on Theory of Computing (STOC 2023), June 20–23, 2023, Orlando, FL, USA

STOC 2023 – Proceedings

Contents - Abstracts - Authors

Frontmatter

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

Session 1A

Almost Chor-Goldreich Sources and Adversarial Random Walks
Dean Doron ORCID logo, Dana Moshkovitz ORCID logo, Justin Oh ORCID logo, and David Zuckerman ORCID logo
(Ben-Gurion University of the Negev, Israel; University of Texas at Austin, USA)
Publisher's Version
A New Berry-Esseen Theorem for Expander Walks
Louis Golowich ORCID logo
(University of California at Berkeley, Berkeley, USA)
Publisher's Version
Near-Optimal Derandomization of Medium-Width Branching Programs
Aaron (Louie) Putterman ORCID logo and Edward Pyne ORCID logo
(Harvard University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
Approximating Iterated Multiplication of Stochastic Matrices in Small Space
Gil Cohen ORCID logo, Dean Doron ORCID logo, Ori Sberlo ORCID logo, and Amnon Ta-Shma ORCID logo
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel)
Publisher's Version
Extractors for Images of Varieties
Zeyu Guo ORCID logo, Ben Lee Volk ORCID logo, Akhil Jalan ORCID logo, and David Zuckerman ORCID logo
(Ohio State University, USA; Reichman University, Israel; University of Texas at Austin, USA)
Publisher's Version
When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems
Lijie Chen ORCID logo and Roei Tell ORCID logo
(University of California at Berkeley, Berkeley, USA; Institute for Advanced Study, Princeton, USA; Rutgers University, USA)
Publisher's Version
Hardness Self-Amplification: Simplified, Optimized, and Unified
Shuichi Hirahara ORCID logo and Nobutaka Shimizu ORCID logo
(National Institute of Informatics, Japan; Tokyo Institute of Technology, Japan)
Publisher's Version
Sum-of-Squares Lower Bounds for Densest k-Subgraph
Chris Jones ORCID logo, Aaron Potechin ORCID logo, Goutham Rajendran ORCID logo, and Jeff Xu ORCID logo
(Bocconi University, Italy; University of Chicago, USA; Carnegie Mellon University, USA)
Publisher's Version
Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
Elchanan Mossel ORCID logo, Allan Sly ORCID logo, and Youngtak Sohn ORCID logo
(Massachusetts Institute of Technology, USA; Princeton University, USA)
Publisher's Version
Parallel Discrete Sampling via Continuous Walks
Nima Anari ORCID logo, Yizhi Huang ORCID logo, Tianyu Liu ORCID logo, Thuy-Duong Vuong ORCID logo, Brian Xu ORCID logo, and Katherine Yu ORCID logo
(Stanford University, USA; Tsinghua University, China)
Publisher's Version
Sampling from Convex Sets with a Cold Start using Multiscale Decompositions
Hariharan Narayanan ORCID logo, Amit Rajaraman ORCID logo, and Piyush Srivastava ORCID logo
(TIFR, Mumbai, India; IIT Bombay, India)
Publisher's Version

Session 1B

On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Sepehr Assadi ORCID logo, Soheil Behnezhad ORCID logo, Sanjeev Khanna ORCID logo, and Huan Li ORCID logo
(Rutgers University, USA; Northeastern University, USA; University of Pennsylvania, USA)
Publisher's Version
Optimal Eigenvalue Approximation via Sketching
William Swartworth ORCID logo and David P. Woodruff ORCID logo
(University of California at Los Angeles, Los Angeles, USA; Carnegie Mellon University, USA)
Publisher's Version
Streaming Euclidean MST to a Constant Factor
Xi ChenORCID logo, Vincent Cohen-Addad ORCID logo, Rajesh Jayaram ORCID logo, Amit Levi ORCID logo, and Erik Waingarten ORCID logo
(Columbia University, USA; Google Research, Switzerland; Google Research, USA; University of Waterloo, Canada; University of Pennsylvania, USA)
Publisher's Version
Streaming Euclidean Max-Cut: Dimension vs Data Reduction
Xiaoyu Chen ORCID logo, Shaofeng H.-C. Jiang ORCID logo, and Robert Krauthgamer ORCID logo
(Peking University, China; Weizmann Institute of Science, Israel)
Publisher's Version
(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
Sepehr Assadi ORCID logo and Janani Sundaresan ORCID logo
(Rutgers University, USA)
Publisher's Version
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
Arun Jambulapati ORCID logo, Yang P. LiuORCID logo, and Aaron Sidford ORCID logo
(University of Washington, USA; Stanford University, USA)
Publisher's Version
Spectral Hypergraph Sparsification via Chaining
James R. Lee ORCID logo
(University of Washington, USA)
Publisher's Version
Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching
Sudatta Bhattacharya ORCID logo and Michal Koucký ORCID logo
(Charles University, Prague, Czechia)
Publisher's Version
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester
Hadley Black ORCID logo, Deeparnab Chakrabarty ORCID logo, and C. Seshadhri ORCID logo
(University of California at Los Angeles, Los Angeles, USA; Dartmouth College, USA; University of California at Santa Cruz, Santa Cruz, USA)
Publisher's Version
Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation
Mahsa Derakhshan ORCID logo, Naveen Durvasula ORCID logo, and Nika Haghtalab ORCID logo
(Northeastern University, USA; University of California at Berkeley, Berkeley, USA)
Publisher's Version
Sublinear Algorithms for (1.5+𝜖)-Approximate Matching
Sayan Bhattacharya ORCID logo, Peter Kiss ORCID logo, and Thatchaphol SaranurakORCID logo
(University of Warwick, UK; MPI-INF, Germany; University of Michigan, USA)
Publisher's Version
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Soheil Behnezhad ORCID logo, Mohammad Roghani ORCID logo, and Aviad Rubinstein ORCID logo
(Northeastern University, USA; Stanford University, USA)
Publisher's Version

Session 1C

Almost-Optimal Sublinear Additive Spanners
Zihan Tan ORCID logo and Tianyi Zhang ORCID logo
(Rutgers University, USA; Tel Aviv University, Israel)
Publisher's Version
A Unified Framework for Light Spanners
Hung LeORCID logo and Shay Solomon ORCID logo
(University of Massachusetts, USA; Tel Aviv University, Israel)
Publisher's Version
New Algorithms for All Pairs Approximate Shortest Paths
Liam Roditty ORCID logo
(Bar-Ilan University, Israel)
Publisher's Version
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Václav Rozhoň ORCID logo, Bernhard Haeupler ORCID logo, Anders Martinsson ORCID logo, Christoph Grunau ORCID logo, and Goran Zuzic ORCID logo
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)
Publisher's Version
A New Approach to Learning Linear Dynamical Systems
Ainesh Bakshi ORCID logo, Allen Liu ORCID logo, Ankur Moitra ORCID logo, and Morris Yau ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
Planning and Learning in Partially Observable Systems via Filter Stability
Noah GolowichORCID logo, Ankur Moitra ORCID logo, and Dhruv Rohatgi ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making
Qinghua Liu ORCID logo, Praneeth Netrapalli ORCID logo, Csaba Szepesvari ORCID logo, and Chi Jin ORCID logo
(Princeton University, USA; Google Research, India; DeepMind, UK; University of Alberta, Canada)
Publisher's Version Info
Weighted Edit Distance Computation: Strings, Trees, and Dyck
Debarati Das ORCID logo, Jacob Gilbert ORCID logo, MohammadTaghi Hajiaghayi ORCID logo, Tomasz Kociumaka ORCID logo, and Barna Saha ORCID logo
(Pennsylvania State University, USA; University of Maryland, USA; MPI-INF, Germany; University of California at San Diego, San Diego, USA)
Publisher's Version
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
Amir Abboud ORCID logo, Karl Bringmann ORCID logo, and Nick Fischer ORCID logo
(Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany)
Publisher's Version
Removing Additive Structure in 3SUM-Based Reductions
Ce JinORCID logo and Yinzhan Xu ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
Timothy M. Chan ORCID logo, Virginia Vassilevska Williams ORCID logo, and Yinzhan Xu ORCID logo
(University of Illinois at Urbana-Champaign, USA; Massachusetts Institute of Technology, USA)
Publisher's Version

Session 2A

Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝
Xiaorui Sun ORCID logo
(University of Illinois at Chicago, USA)
Publisher's Version
Linear Independence, Alternants, and Applications
Vishwas Bhargava ORCID logo, Shubhangi Saraf ORCID logo, and Ilya Volkovich ORCID logo
(University of Waterloo, Canada; University of Toronto, Canada; Boston College, USA)
Publisher's Version Info
Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity
Josh Alman ORCID logo and Kevin Rao ORCID logo
(Columbia University, USA)
Publisher's Version
A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications
Hamed Hatami ORCID logo, Kaave Hosseini ORCID logo, and Xiang Meng ORCID logo
(McGill University, Canada; University of Rochester, USA)
Publisher's Version

Session 2B

Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
Edith Cohen ORCID logo, Xin Lyu ORCID logo, Jelani Nelson ORCID logo, Tamás Sarlós ORCID logo, and Uri Stemmer ORCID logo
(Google Research, USA; Tel Aviv University, Israel; University of California at Berkeley, Berkeley, USA; Google Research, Israel)
Publisher's Version Info
Privately Estimating a Gaussian: Efficient, Robust, and Optimal
Daniel Alabi ORCID logo, Pravesh K. Kothari ORCID logo, Pranay Tankala ORCID logo, Prayaag Venkat ORCID logo, and Fred Zhang ORCID logo
(Columbia University, USA; Carnegie Mellon University, USA; Harvard University, USA; University of California at Berkeley, Berkeley, USA)
Publisher's Version
Robustness Implies Privacy in Statistical Estimation
Samuel B. HopkinsORCID logo, Gautam KamathORCID logo, Mahbod MajidORCID logo, and Shyam NarayananORCID logo
(Massachusetts Institute of Technology, USA; University of Waterloo, Canada; Carnegie Mellon University, USA)
Publisher's Version
Concurrent Composition Theorems for Differential Privacy
Salil Vadhan ORCID logo and Wanrong Zhang ORCID logo
(Harvard University, USA)
Publisher's Version
Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Mark Bun ORCID logo, Marco Gaboardi ORCID logo, Max Hopkins ORCID logo, Russell Impagliazzo ORCID logo, Rex Lei ORCID logo, Toniann Pitassi ORCID logo, Satchit Sivakumar ORCID logo, and Jessica Sorrell ORCID logo
(Boston University, USA; University of California at San Diego, San Diego, USA; Columbia University, USA; University of Pennsylvania, USA)
Publisher's Version

Session 2C

An Improved Parameterized Algorithm for Treewidth
Tuukka KorhonenORCID logo and Daniel Lokshtanov ORCID logo
(University of Bergen, Norway, Norway; University of California at Santa Barbara, Santa Barbara, USA)
Publisher's Version
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan ORCID logo, Matthias Lanzinger ORCID logo, and Marc Roth ORCID logo
(University of Milan, Italy; University of Oxford, UK)
Publisher's Version
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms
Huck Bennett ORCID logo, Mahdi Cheraghchi ORCID logo, Venkatesan Guruswami ORCID logo, and João RibeiroORCID logo
(Oregon State University, USA; University of Michigan, USA; University of California at Berkeley, Berkeley, USA; NOVA-LINCS, Portugal; Universidade Nova de Lisboa, Portugal)
Publisher's Version
First-Order Model Checking on Structurally Sparse Graph Classes
Jan Dreier ORCID logo, Nikolas Mählmann ORCID logo, and Sebastian Siebertz ORCID logo
(TU Wien, Austria; University of Bremen, Germany)
Publisher's Version

Session 3: Best Papers

The Randomized 𝑘-Server Conjecture Is False!
Sébastien BubeckORCID logo, Christian Coester ORCID logo, and Yuval Rabani ORCID logo
(Microsoft Research, USA; University of Oxford, UK; Hebrew University of Jerusalem, Israel)
Publisher's Version
Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
Wei-Kai Lin ORCID logo, Ethan Mook ORCID logo, and Daniel WichsORCID logo
(Northeastern University, USA; NTT Research, USA)
Publisher's Version

Session 4A

SDPs and Robust Satisfiability of Promise CSP
Joshua Brakensiek ORCID logo, Venkatesan Guruswami ORCID logo, and Sai Sandeep ORCID logo
(Stanford University, USA; University of California at Berkeley, Berkeley, USA)
Publisher's Version
Approximate Graph Colouring and the Hollow Shadow
Lorenzo Ciardo ORCID logo and Stanislav Živný ORCID logo
(University of Oxford, UK)
Publisher's Version
On Approximability of Satisfiable k-CSPs: II
Amey Bhangale ORCID logo, Subhash Khot ORCID logo, and Dor Minzer ORCID logo
(University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
On Approximability of Satisfiable k-CSPs: III
Amey Bhangale ORCID logo, Subhash Khot ORCID logo, and Dor Minzer ORCID logo
(University of California at Riverside, Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
An Analogue of Bonami’s Lemma for Functions on Spaces of Linear Maps, and 2-2 Games
David Ellis ORCID logo, Guy Kindler ORCID logo, and Noam Lifshitz ORCID logo
(University of Bristol, UK; Hebrew University of Jerusalem, Israel)
Publisher's Version
Noise Stability on the Boolean Hypercube via a Renormalized Brownian Motion
Ronen Eldan ORCID logo, Dan Mikulincer ORCID logo, and Prasad RaghavendraORCID logo
(Microsoft Research, USA; Weizmann Institute of Science, Israel; Massachusetts Institute of Technology, USA; University of California at Berkeley, Berkeley, USA)
Publisher's Version

Session 4B

A Proof of the Nisan-Ronen Conjecture
George Christodoulou ORCID logo, Elias Koutsoupias ORCID logo, and Annamária Kovács ORCID logo
(Aristotle University of Thessaloniki, Greece; RC Athena, Greece; University of Oxford, UK; Goethe University, Frankfurt am Main, Germany)
Publisher's Version
A Constant Factor Prophet Inequality for Online Combinatorial Auctions
José Correa ORCID logo and Andrés Cristi ORCID logo
(University of Chile, Chile)
Publisher's Version
Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules
Xi ChenORCID logo and Binghui Peng ORCID logo
(Columbia University, USA)
Publisher's Version
Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming
Ioannis CaragiannisORCID logo and Zhile Jiang ORCID logo
(Aarhus University, Denmark)
Publisher's Version
Credible Decentralized Exchange Design via Verifiable Sequencing Rules
Matheus Venturyne Xavier FerreiraORCID logo and David C. Parkes ORCID logo
(Harvard University, USA)
Publisher's Version
On the Optimal Fixed-Price Mechanism in Bilateral Trade
Yang Cai ORCID logo and Jinzhao Wu ORCID logo
(Yale University, USA)
Publisher's Version
Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades
Zhengyang Liu ORCID logo, Zeyu Ren ORCID logo, and Zihe Wang ORCID logo
(Beijing Institute of Technology, China; Renmin University of China, China)
Publisher's Version

Session 4C

Improved and Deterministic Online Service with Deadlines or Delay
Noam Touitou ORCID logo
(Amazon, Israel)
Publisher's Version
Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
Ravishankar Krishnaswamy ORCID logo, Shi Li ORCID logo, and Varun Suriyanarayana ORCID logo
(Microsoft Research, India; University at Buffalo, USA; Cornell University, USA)
Publisher's Version
Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
Hu FuORCID logo, Jiawei Li ORCID logo, and Daogao LiuORCID logo
(Shanghai University of Finance and Economics, China; University of Texas at Austin, USA; University of Washington, USA)
Publisher's Version
Pandora’s Problem with Nonobligatory Inspection: Optimal Structure and a PTAS
Hedyeh Beyhaghi ORCID logo and Linda Cai ORCID logo
(Carnegie Mellon University, USA; Princeton University, USA)
Publisher's Version
Local and Global Expansion in Random Geometric Graphs
Siqi Liu ORCID logo, Sidhanth Mohanty ORCID logo, Tselil Schramm ORCID logo, and Elizabeth Yang ORCID logo
(University of California at Berkeley, Berkeley, USA; Stanford University, USA)
Publisher's Version Info
New High Dimensional Expanders from Covers
Yotam Dikstein ORCID logo
(Weizmann Institute of Science, Israel)
Publisher's Version
Towards the Erdős-Gallai Cycle Decomposition Conjecture
Matija Bucić ORCID logo and Richard Montgomery ORCID logo
(Institute for Advanced Study, Princeton, USA; Princeton University, USA; University of Warwick, UK)
Publisher's Version Video

Session 5A

An Optimal “It Ain’t Over Till It’s Over” Theorem
Ronen Eldan ORCID logo, Avi Wigderson ORCID logo, and Pei Wu ORCID logo
(Microsoft Research, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study, Princeton, USA)
Publisher's Version
Randomized versus Deterministic Decision Tree Size
Arkadev Chattopadhyay ORCID logo, Yogesh Dahiya ORCID logo, Nikhil S. Mande ORCID logo, Jaikumar Radhakrishnan ORCID logo, and Swagato Sanyal ORCID logo
(TIFR, Mumbai, India; IMSc, Chennai, India; QuSoft, Netherlands; CWI, Amsterdam, Netherlands; ICTS, Bengaluru, India; IIT Kharagpur, India)
Publisher's Version
Optimal Explicit Small-Depth Formulas for the Coin Problem
Srikanth Srinivasan ORCID logo and Utkarsh Tripathi ORCID logo
(Aarhus University, Denmark; IIT Bombay, India)
Publisher's Version
Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees
Pooya Hatami ORCID logo, William M. Hoza ORCID logo, Avishay Tal ORCID logo, and Roei Tell ORCID logo
(Ohio State University, USA; University of California at Berkeley, Berkeley, USA; Simons Institute for the Theory of Computing, Berkeley, USA; Institute for Advanced Study, Princeton, USA; Rutgers University, USA)
Publisher's Version

Session 5B

Good Quantum LDPC Codes with Linear Time Decoders
Irit Dinur ORCID logo, Min-Hsiu Hsieh ORCID logo, Ting-Chun Lin ORCID logo, and Thomas Vidick ORCID logo
(Weizmann Institute of Science, Israel; Hon Hai Research Institute, Taiwan; University of California at San Diego, San Diego, USA; California Institute of Technology, USA)
Publisher's Version
An Efficient Decoder for a Linear Distance Quantum LDPC Code
Shouzhen Gu ORCID logo, Christopher A. Pattison ORCID logo, and Eugene Tang ORCID logo
(California Institute of Technology, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
Certified Randomness from Quantum Supremacy
Scott Aaronson ORCID logo and Shih-Han Hung ORCID logo
(University of Texas at Austin, USA)
Publisher's Version
A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling
Dorit Aharonov ORCID logo, Xun Gao ORCID logo, Zeph Landau ORCID logo, Yunchao Liu ORCID logo, and Umesh Vazirani ORCID logo
(Hebrew University of Jerusalem, Israel; Harvard University, USA; University of California at Berkeley, Berkeley, USA)
Publisher's Version

Session 5C

Nearly All 𝑘-SAT Functions Are Unate
József Balogh ORCID logo, Dingding Dong ORCID logo, Bernard Lidický ORCID logo, Nitya Mani ORCID logo, and Yufei Zhao ORCID logo
(University of Illinois at Urbana-Champaign, USA; Harvard University, USA; Iowa State University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version Info
Kneser Graphs Are Hamiltonian
Arturo Merino ORCID logo, Torsten Mütze ORCID logo, and Namrata ORCID logo
(TU Berlin, Germany; University of Warwick, UK)
Publisher's Version
Random Walks on Rotating Expanders
Gil Cohen ORCID logo and Gal Maor ORCID logo
(Tel Aviv University, Israel)
Publisher's Version
Algorithmic Applications of Hypergraph and Partition Containers
Or Zamir ORCID logo
(Princeton University, USA)
Publisher's Version

Session 6: Best Student Papers

Subsampling Suffices for Adaptive Data Analysis
Guy Blanc ORCID logo
(Stanford University, USA)
Publisher's Version Info
The Power of Multi-step Vizing Chains
Aleksander Bjørn Grodt Christiansen ORCID logo
(DTU, Denmark)
Publisher's Version

Session 7A

Capturing One-Way Functions via NP-Hardness of Meta-Complexity
Shuichi Hirahara ORCID logo
(National Institute of Informatics, Japan)
Publisher's Version
A Duality between One-Way Functions and Average-Case Symmetry of Information
Shuichi Hirahara ORCID logo, Rahul IlangoORCID logo, Zhenjian Lu ORCID logo, Mikito Nanashima ORCID logo, and Igor C. OliveiraORCID logo
(National Institute of Informatics, Japan; Massachusetts Institute of Technology, USA; University of Oxford, UK; Tokyo Institute of Technology, Japan; University of Warwick, UK)
Publisher's Version
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
Jiatu LiORCID logo and Igor C. OliveiraORCID logo
(Tsinghua University, China; University of Warwick, UK)
Publisher's Version
Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
Yeyuan Chen ORCID logo, Yizhi Huang ORCID logo, Jiatu Li ORCID logo, and Hanlin RenORCID logo
(Xi’an Jiaotong University, China; Tsinghua University, China; University of Oxford, UK)
Publisher's Version
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
Yizhi Huang ORCID logo, Rahul IlangoORCID logo, and Hanlin RenORCID logo
(Tsinghua University, China; Massachusetts Institute of Technology, USA; University of Oxford, UK)
Publisher's Version
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
Rahul IlangoORCID logo, Jiatu LiORCID logo, and R. Ryan Williams ORCID logo
(Massachusetts Institute of Technology, USA; Tsinghua University, China)
Publisher's Version

Session 7B

NLTS Hamiltonians from Good Quantum Codes
Anurag Anshu ORCID logo, Nikolas P. Breuckmann ORCID logo, and Chinmay Nirkhe ORCID logo
(Harvard University, USA; University of Bristol, UK; MIT-IBM Watson AI Lab, USA)
Publisher's Version
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory
Qipeng Liu ORCID logo, Ran Raz ORCID logo, and Wei Zhan ORCID logo
(Simons Institute for the Theory of Computing, Berkeley, USA; Princeton University, USA)
Publisher's Version
Quantum Depth in the Random Oracle Model
Atul Singh Arora ORCID logo, Andrea ColadangeloORCID logo, Matthew Coudron ORCID logo, Alexandru Gheorghiu ORCID logo, Uttam Singh ORCID logo, and Hendrik Waldner ORCID logo
(California Institute of Technology, USA; University of Washington, USA; National Institute of Standards and Technology, USA; University of Maryland, USA; Chalmers University of Technology, Sweden; ETH Zurich, Switzerland; Polish Academy of Sciences, Poland; IIIT Hyderabad, India; University of Maryland, College Park, USA; MPI-SP, Germany)
Publisher's Version
Multidimensional Quantum Walks
Stacey Jeffery ORCID logo and Sebastian Zur ORCID logo
(CWI, Amsterdam, Netherlands; QuSoft, Netherlands)
Publisher's Version
Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End
Alexander M. Dalzell ORCID logo, Nicola Pancotti ORCID logo, Earl T. Campbell ORCID logo, and Fernando G.S.L. Brandão ORCID logo
(AWS Center for Quantum Computing, USA; California Institute of Technology, USA; Riverlane, UK; University of Sheffield, UK)
Publisher's Version
Approximating Binary Longest Common Subsequence in Almost-Linear Time
Xiaoyu He ORCID logo and Ray Li ORCID logo
(Princeton University, USA; University of California at Berkeley, Berkeley, USA)
Publisher's Version

Session 7C

A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths
Julia Chuzhoy ORCID logo and Ruimin Zhang ORCID logo
(Toyota Technological Institute at Chicago, USA; University of Chicago, USA)
Publisher's Version
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
Sebastian Forster ORCID logo, Yasamin Nazari ORCID logo, and Maximilian Probst Gutenberg ORCID logo
(University of Salzburg, Austria; ETH Zurich, Switzerland)
Publisher's Version
Dynamic ((1+𝜖) ln 𝑛)-Approximation Algorithms for Minimum Set Cover and Dominating Set
Shay Solomon ORCID logo and Amitai Uzrad ORCID logo
(Tel Aviv University, Israel)
Publisher's Version
Improved Dynamic Colouring of Sparse Graphs
Aleksander Bjørn Grodt Christiansen ORCID logo, Krzysztof Nowicki ORCID logo, and Eva Rotenberg ORCID logo
(DTU, Denmark; University of Copenhagen, Denmark; pathway.com, Poland)
Publisher's Version
Dynamic Maxflow via Dynamic Interior Point Methods
Jan van den Brand ORCID logo, Yang P. LiuORCID logo, and Aaron Sidford ORCID logo
(Georgia Institute of Technology, USA; Stanford University, USA)
Publisher's Version
Fast Algorithms via Dynamic-Oracle Matroids
Joakim Blikstad ORCID logo, Sagnik Mukhopadhyay ORCID logo, Danupon NanongkaiORCID logo, and Ta-Wei Tu ORCID logo
(KTH Royal Institute of Technology, Sweden; University of Sheffield, UK; MPI-INF, Germany)
Publisher's Version

Session 8A

Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
Riddhi Ghosal ORCID logo, Yuval Ishai ORCID logo, Alexis Korb ORCID logo, Eyal Kushilevitz ORCID logo, Paul Lou ORCID logo, and Amit Sahai ORCID logo
(University of California at Los Angeles, Los Angeles, USA; Technion, Israel)
Publisher's Version
On the Consistency of Circuit Lower Bounds for Non-deterministic Time
Albert Atserias ORCID logo, Sam Buss ORCID logo, and Moritz Müller ORCID logo
(Universitat Politècnica de Catalunya, Spain; Centre de Recerca Matemàtica, Spain; University of California at San Diego, San Diego, USA; University of Passau, Germany)
Publisher's Version
Shellability Is Hard Even for Balls
Pavel Paták ORCID logo and Martin Tancer ORCID logo
(Charles University, Prague, Czechia; Czech Technical University, Prague, Czechia)
Publisher's Version
The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3
Jin-Yi Cai ORCID logo and Ashwin Maran ORCID logo
(University of Wisconsin-Madison, USA)
Publisher's Version

Session 8B

Approximating Nash Social Welfare by Matching and Local Search
Jugal GargORCID logo, Edin HusićORCID logo, Wenzheng Li ORCID logo, László A. VéghORCID logo, and Jan Vondrák ORCID logo
(University of Illinois at Urbana-Champaign, USA; USI Lugano, Switzerland; Stanford University, USA; London School of Economics, UK)
Publisher's Version
Multi-agent Contracts
Paul Dütting ORCID logo, Tomer Ezra ORCID logo, Michal Feldman ORCID logo, and Thomas Kesselheim ORCID logo
(Google Research, Switzerland; Sapienza University of Rome, Italy; Tel Aviv University, Israel; Microsoft Research, Israel; University of Bonn, Germany)
Publisher's Version
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
Tobias Friedrich ORCID logo, Davis Issac ORCID logo, Nikhil Kumar ORCID logo, Nadym Mallek ORCID logo, and Ziena Zeif ORCID logo
(Hasso Plattner Institute, Potsdam, Germany)
Publisher's Version
A PTAS for Minimizing Weighted Flow Time on a Single Machine
Alexander Armbruster ORCID logo, Lars Rohwedder ORCID logo, and Andreas Wiese ORCID logo
(TU Munich, Germany; Maastricht University, Netherlands)
Publisher's Version

Session 8C

Random Graph Matching at Otter’s Threshold via Counting Chandeliers
Cheng MaoORCID logo, Yihong WuORCID logo, Jiaming XuORCID logo, and Sophie H. YuORCID logo
(Georgia Institute of Technology, USA; Yale University, USA; Duke University, USA)
Publisher's Version
Uniformly Random Colourings of Sparse Graphs
Eoin Hurley ORCID logo and François Pirot ORCID logo
(Unaffiliated, Heidelberg, Germany; Université Paris-Saclay, France)
Publisher's Version
Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast
Bernhard Haeupler ORCID logo, D. Ellis Hershkowitz ORCID logo, and Thatchaphol SaranurakORCID logo
(ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of Michigan, USA)
Publisher's Version
Tight Conditional Lower Bounds for Vertex Connectivity Problems
Zhiyi Huang ORCID logo, Yaowei Long ORCID logo, Thatchaphol SaranurakORCID logo, and Benyu Wang ORCID logo
(Tsinghua University, China; University of Michigan, USA)
Publisher's Version

Session 9A

Approximate Distance Sensitivity Oracles in Subquadratic Space
Davide Bilò ORCID logo, Shiri Chechik ORCID logo, Keerti Choudhary ORCID logo, Sarel Cohen ORCID logo, Tobias Friedrich ORCID logo, Simon Krogmann ORCID logo, and Martin Schirneck ORCID logo
(University of L’Aquila, Italy; Tel Aviv University, Israel; IIT Delhi, India; Academic College of Tel Aviv-Yaffo, Israel; Hasso Plattner Institute, Potsdam, Germany; University of Vienna, Austria)
Publisher's Version
External Memory Fully Persistent Search Trees
Gerth Stølting Brodal ORCID logo, Casper Moldrup Rysgaard ORCID logo, and Rolf Svenning ORCID logo
(Aarhus University, Denmark)
Publisher's Version
The Rate of Interactive Codes Is Bounded Away from 1
Klim Efremenko ORCID logo, Gillat Kol ORCID logo, Dmitry Paramonov ORCID logo, and Raghuvansh R. Saxena ORCID logo
(Ben-Gurion University of the Negev, Israel; Princeton University, USA; Microsoft Research, USA)
Publisher's Version
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
Omar Alrabiah ORCID logo, Venkatesan Guruswami ORCID logo, Pravesh K. Kothari ORCID logo, and Peter Manohar ORCID logo
(University of California at Berkeley, Berkeley, USA; Carnegie Mellon University, USA)
Publisher's Version
Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel
Meghal Gupta ORCID logo and Rachel Yun Zhang ORCID logo
(University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
A High Dimensional Goldreich-Levin Theorem
Parker Newton ORCID logo, Silas Richelson ORCID logo, and Chase Wilson ORCID logo
(University of California at Riverside, Riverside, USA; University of California at San Diego, San Diego, USA)
Publisher's Version
Binary Error-Correcting Codes with Minimal Noiseless Feedback
Meghal GuptaORCID logo, Venkatesan Guruswami ORCID logo, and Rachel Yun Zhang ORCID logo
(University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
Generic Reed-Solomon Codes Achieve List-Decoding Capacity
Joshua Brakensiek ORCID logo, Sivakanth Gopi ORCID logo, and Visu Makam ORCID logo
(Stanford University, USA; Microsoft Research, USA; Radix Trading Europe, Netherlands)
Publisher's Version
Optimal Bounds for Noisy Sorting
Yuzhou Gu ORCID logo and Yinzhan Xu ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
Lattice Problems beyond Polynomial Time
Divesh Aggarwal ORCID logo, Huck Bennett ORCID logo, Zvika Brakerski ORCID logo, Alexander Golovnev ORCID logo, Rajendra Kumar ORCID logo, Zeyong Li ORCID logo, Spencer Peters ORCID logo, Noah Stephens-Davidowitz ORCID logo, and Vinod Vaikuntanathan ORCID logo
(National University of Singapore, Singapore; Oregon State University, USA; Weizmann Institute of Science, Israel; Georgetown University, USA; Cornell University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version

Session 9B

The Round Complexity of Statistical MPC with Optimal Resiliency
Benny Applebaum ORCID logo, Eliran Kachlon ORCID logo, and Arpita Patra ORCID logo
(Tel Aviv University, Israel; IISc Bangalore, India)
Publisher's Version
Constant-Round Arguments from One-Way Functions
Noga Amit ORCID logo and Guy N. RothblumORCID logo
(Weizmann Institute of Science, Israel; Apple, USA)
Publisher's Version
Boosting Batch Arguments and RAM Delegation
Yael KalaiORCID logo, Alex LombardiORCID logo, Vinod VaikuntanathanORCID logo, and Daniel WichsORCID logo
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA; Northeastern University, USA; NTT Research, USA)
Publisher's Version
Succinct Computational Secret Sharing
Benny Applebaum ORCID logo, Amos Beimel ORCID logo, Yuval Ishai ORCID logo, Eyal Kushilevitz ORCID logo, Tianren Liu ORCID logo, and Vinod VaikuntanathanORCID logo
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel; Technion, Israel; Peking University, China; Massachusetts Institute of Technology, USA)
Publisher's Version
Obfuscation of Pseudo-Deterministic Quantum Circuits
James Bartusek ORCID logo, Fuyuki Kitagawa ORCID logo, Ryo Nishimaki ORCID logo, and Takashi Yamakawa ORCID logo
(University of California at Berkeley, Berkeley, USA; NTT Social Informatics Laboratories, Japan)
Publisher's Version
Commitments to Quantum States
Sam Gunn ORCID logo, Nathan Ju ORCID logo, Fermi Ma ORCID logo, and Mark Zhandry ORCID logo
(University of California at Berkeley, Berkeley, USA; Simons Institute for the Theory of Computing, Berkeley, USA; NTT Research, USA)
Publisher's Version
Quantum Cryptography in Algorithmica
William Kretschmer ORCID logo, Luowen Qian ORCID logo, Makrand Sinha ORCID logo, and Avishay Tal ORCID logo
(University of Texas at Austin, USA; Boston University, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA)
Publisher's Version
Quantum Free Games
Anand Natarajan ORCID logo and Tina Zhang ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
Quantum Advantage from Any Non-local Game
Yael KalaiORCID logo, Alex LombardiORCID logo, Vinod VaikuntanathanORCID logo, and Lisa Yang ORCID logo
(Microsoft Research, USA; Massachusetts Institute of Technology, USA; Simons Institute for the Theory of Computing, Berkeley, USA; University of California at Berkeley, Berkeley, USA)
Publisher's Version
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
Fernando Granha Jeronimo ORCID logo and Pei Wu ORCID logo
(Institute for Advanced Study, Princeton, USA)
Publisher's Version

Session 9C

Testing Distributional Assumptions of Learning Algorithms
Ronitt Rubinfeld ORCID logo and Arsen Vasilyan ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version Info
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
Aravind Gollakota ORCID logo, Adam R. Klivans ORCID logo, and Pravesh K. Kothari ORCID logo
(University of Texas at Austin, USA; Carnegie Mellon University, USA)
Publisher's Version
Learning Polynomial Transformations via Generalized Tensor Decompositions
Sitan Chen ORCID logo, Jerry Li ORCID logo, Yuanzhi Li ORCID logo, and Anru R. Zhang ORCID logo
(University of California at Berkeley, Berkeley, USA; Harvard University, USA; Microsoft Research, USA; Carnegie Mellon University, USA; Duke University, USA)
Publisher's Version
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
Alexander S. Wein ORCID logo
(University of California at Davis, Davis, USA)
Publisher's Version
What Makes a Good Fisherman? Linear Regression under Self-Selection Bias
Yeshwanth Cherapanamjeri ORCID logo, Constantinos Daskalakis ORCID logo, Andrew IlyasORCID logo, and Manolis Zampetakis ORCID logo
(University of California at Berkeley, Berkeley, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
A Characterization of List Learnability
Moses Charikar ORCID logo and Chirag Pabbaraju ORCID logo
(Stanford University, USA)
Publisher's Version
A Unifying Theory of Distance from Calibration
Jarosław Błasiok ORCID logo, Parikshit Gopalan ORCID logo, Lunjia Hu ORCID logo, and Preetum Nakkiran ORCID logo
(Columbia University, USA; Apple, USA; Stanford University, USA)
Publisher's Version
A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning
Ilias Diakonikolas ORCID logo, Christos Tzamos ORCID logo, and Daniel M. Kane ORCID logo
(University of Wisconsin-Madison, USA; University of Athens, Greece; University of California at San Diego, San Diego, USA)
Publisher's Version
Lifting Uniform Learners via Distributional Decomposition
Guy Blanc ORCID logo, Jane Lange ORCID logo, Ali Malik ORCID logo, and Li-Yang Tan ORCID logo
(Stanford University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version Info
Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis
André Lieutier ORCID logo and Mathijs Wintraecken ORCID logo
(No affiliation, France; Université Côte d’Azur, France; Inria, France; IST Austria, Austria)
Publisher's Version

Session 10A

Faster Deterministic Distributed MIS and Approximate Matching
Mohsen Ghaffari ORCID logo and Christoph Grunau ORCID logo
(Massachusetts Institute of Technology, USA; ETH Zurich, Switzerland)
Publisher's Version
Finding a Small Vertex Cut on Distributed Networks
Yonggang Jiang ORCID logo and Sagnik Mukhopadhyay ORCID logo
(MPI-INF, Germany; Saarland University, Germany; University of Sheffield, UK)
Publisher's Version
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online
David P. Woodruff ORCID logo and Taisuke Yasuda ORCID logo
(Carnegie Mellon University, USA)
Publisher's Version
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank
Nikhil Bansal ORCID logo, Haotian Jiang ORCID logo, and Raghu Meka ORCID logo
(University of Michigan, Ann Arbor, USA; Microsoft Research, USA; University of California at Los Angeles, Los Angeles, USA)
Publisher's Version

Session 10B

A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation
Vera Traub ORCID logo and Rico Zenklusen ORCID logo
(University of Bonn, Germany; ETH Zurich, Switzerland)
Publisher's Version
Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues
Lap Chi Lau ORCID logo, Kam Chuen Tung ORCID logo, and Robert Wang ORCID logo
(University of Waterloo, Canada)
Publisher's Version
An Improved Approximation Guarantee for Prize-Collecting TSP
Jannis Blauth ORCID logo and Martin Nägele ORCID logo
(University of Bonn, Germany)
Publisher's Version
Better Trees for Santa Claus
Étienne Bamas ORCID logo and Lars Rohwedder ORCID logo
(EPFL, Switzerland; Maastricht University, Netherlands)
Publisher's Version

Session 10C

Interior Point Methods with a Gradient Oracle
Adrian Vladu ORCID logo
(CNRS, France; IRIF, France; Université Paris Cité, France)
Publisher's Version
The Smoothed Complexity of Policy Iteration for Markov Decision Processes
Miranda Christ ORCID logo and Mihalis Yannakakis ORCID logo
(Columbia University, USA)
Publisher's Version
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
Sophie Huiberts ORCID logo, Yin Tat Lee ORCID logo, and Xinzhi Zhang ORCID logo
(Columbia University, USA; Microsoft Research, USA; University of Washington, USA)
Publisher's Version
Algorithms Approaching the Threshold for Semi-random Planted Clique
Rares-Darius Buhai ORCID logo, Pravesh K. Kothari ORCID logo, and David Steurer ORCID logo
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)
Publisher's Version

proc time: 22.93