STOC 2022
54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022)
Powered by
Conference Publishing Consulting

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), June 20–24, 2022, Rome, Italy

STOC 2022 – Proceedings

Contents - Abstracts - Authors

Frontmatter

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

Session 1A

Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
Hamoon Mousavi, Seyed Sajjad Nezhadi ORCID logo, and Henry YuenORCID logo
(Columbia University, USA; University of Maryland, USA)
Publisher's Version
An Area Law for 2D Frustration-Free Spin Systems
Anurag Anshu ORCID logo, Itai Arad, and David Gosset ORCID logo
(Harvard University, USA; Technion, Israel; University of Waterloo, Canada)
Publisher's Version
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
Sevag Gharibian and François Le Gall
(Paderborn University, Germany; Nagoya University, Japan)
Publisher's Version
Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
Arjan Cornelissen, Yassine Hamoudi ORCID logo, and Sofiene Jerbi ORCID logo
(University of Amsterdam, Netherlands; University of California at Berkeley, USA; University of Innsbruck, Austria)
Publisher's Version
Distributed Quantum Inner Product Estimation
Anurag Anshu ORCID logo, Zeph Landau ORCID logo, and Yunchao Liu ORCID logo
(Harvard University, USA; University of California at Berkeley, USA)
Publisher's Version

Session 1B

The Power of Two Choices in Graphical Allocation
Nikhil Bansal ORCID logo and Ohad N. Feldheim
(University of Michigan, USA; Hebrew University of Jerusalem, Israel)
Publisher's Version
Expanders via Local Edge Flips in Quasilinear Time
George GiakkoupisORCID logo
(Inria, France; University of Rennes, France; CNRS, France; IRISA, France)
Publisher's Version
(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics
Zhihao Gavin Tang, Jinzhao Wu, and Hongxun Wu
(Shanghai University of Finance and Economics, China; Peking University, China; Tsinghua University, China)
Publisher's Version
The Power of Multiple Choices in Online Stochastic Matching
Zhiyi Huang, Xinkai Shu, and Shuyi Yan
(University of Hong Kong, China; Tsinghua University, China)
Publisher's Version
Online Edge Coloring via Tree Recurrences and Correlation Decay
Janardhan Kulkarni, Yang P. LiuORCID logo, Ashwin Sah ORCID logo, Mehtaab Sawhney, and Jakub Tarnawski
(Microsoft Research, USA; Stanford University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version

Session 1C

The Shortest Even Cycle Problem Is Tractable
Andreas Björklund, Thore Husfeldt ORCID logo, and Petteri Kaski
(Lund University, Sweden; IT University of Copenhagen, Denmark; Aalto University, Finland)
Publisher's Version
Breaking the nk Barrier for Minimum k-Cut on Simple Graphs
Zhiyang He ORCID logo and Jason Li
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)
Publisher's Version
Edge Connectivity Augmentation in Near-Linear Time
Ruoxu Cen, Jason Li, and Debmalya Panigrahi
(Duke University, USA; University of California at Berkeley, USA)
Publisher's Version
Optimal Vertex Connectivity Oracles
Seth PettieORCID logo, Thatchaphol SaranurakORCID logo, and Longhui Yin ORCID logo
(University of Michigan, USA; Tsinghua University, China)
Publisher's Version
Deterministic Massively Parallel Connectivity
Sam Coy and Artur Czumaj
(University of Warwick, UK)
Publisher's Version

Session 2A

Hypercontractivity on High Dimensional Expanders
Tom Gur ORCID logo, Noam Lifshitz ORCID logo, and Siqi Liu ORCID logo
(University of Warwick, UK; Hebrew University of Jerusalem, Israel; University of California at Berkeley, USA)
Publisher's Version
Hypercontractivity on High Dimensional Expanders
Mitali Bafna, Max Hopkins ORCID logo, Tali Kaufman, and Shachar Lovett
(Harvard University, USA; University of California at San Diego, USA; Bar-Ilan University, Israel)
Publisher's Version
Approximate Polymorphisms
Gilad Chase, Yuval FilmusORCID logo, Dor Minzer, Elchanan Mossel ORCID logo, and Nitin Saurabh ORCID logo
(Technion, Israel; Massachusetts Institute of Technology, USA; IIT Hyderabad, India)
Publisher's Version
Learning Low-Degree Functions from a Logarithmic Number of Random Queries
Alexandros EskenazisORCID logo and Paata IvanisviliORCID logo
(University of Cambridge, UK; University of California at Irvine, USA)
Publisher's Version
Positive Spectrahedra: Invariance Principles and Pseudorandom Generators
Srinivasan Arunachalam and Penghui Yao
(IBM Research, USA; Nanjing University, China)
Publisher's Version

Session 2B

New Streaming Algorithms for High Dimensional EMD and MST
Xi ChenORCID logo, Rajesh Jayaram ORCID logo, Amit Levi ORCID logo, and Erik Waingarten ORCID logo
(Columbia University, USA; Google Research, USA; University of Waterloo, Canada; Stanford University, USA)
Publisher's Version
Brooks’ Theorem in Graph Streams: A Single-Pass Semi-streaming Algorithm for ∆-Coloring
Sepehr Assadi ORCID logo, Pankaj Kumar, and Parth Mittal
(Rutgers University, USA; Charles University in Prague, Czechia)
Publisher's Version
Deterministic (1+𝜀)-Approximate Maximum Matching with poly(1/𝜀) Passes in the Semi-streaming Model and Beyond
Manuela Fischer, Slobodan Mitrović, and Jara Uitto
(ETH Zurich, Switzerland; University of California at Davis, USA; Aalto University, Finland)
Publisher's Version Info
Deterministic Graph Coloring in the Streaming Model
Sepehr Assadi ORCID logo, Andrew Chen, and Glenn Sun
(Rutgers University, USA; Cornell University, USA; University of California at Los Angeles, USA)
Publisher's Version
Linear Space Streaming Lower Bounds for Approximating CSPs
Chi-Ning Chou ORCID logo, Alexander Golovnev ORCID logo, Madhu Sudan ORCID logo, Ameya Velingker ORCID logo, and Santhoshini Velusamy ORCID logo
(Harvard University, USA; Georgetown University, USA; Google Research, USA)
Publisher's Version

Session 2C

A PTAS for Unsplittable Flow on a Path
Fabrizio GrandoniORCID logo, Tobias Mömke ORCID logo, and Andreas Wiese ORCID logo
(USI-SUPSI, Switzerland; University of Augsburg, Germany; Vrije Universiteit Amsterdam, Netherlands)
Publisher's Version
A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs
Julia Chuzhoy ORCID logo and Zihan TanORCID logo
(Toyota Technological Institute at Chicago, USA; University of Chicago, USA)
Publisher's Version Info
Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios
Matthias Englert, Nicolaos Matsakis, and Pavel Veselý
(University of Warwick, UK; Charles University in Prague, Czechia)
Publisher's Version
Flow Time Scheduling and Prefix Beck-Fiala
Nikhil Bansal ORCID logo, Lars Rohwedder, and Ola Svensson
(University of Michigan, USA; Maastricht University, Netherlands; EPFL, Switzerland)
Publisher's Version
Bypassing the Surface Embedding: Approximation Schemes for Network Design in Minor-Free Graphs
Vincent Cohen-Addad ORCID logo
(Google Research, Switzerland)
Publisher's Version

Award Papers Session I: Best Papers

Locally Testable Codes with Constant Rate, Distance, and Locality
Irit Dinur ORCID logo, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes
(Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel)
Publisher's Version
Asymptotically Good Quantum and Locally Testable Classical LDPC Codes
Pavel PanteleevORCID logo and Gleb Kalachev ORCID logo
(Lomonosov Moscow State University, Russia)
Publisher's Version

Session 3A

Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals
Robert Andrews ORCID logo and Michael A. Forbes
(University of Illinois at Urbana-Champaign, USA)
Publisher's Version
Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications
Vishwas Bhargava ORCID logo, Sumanta Ghosh, Mrinal Kumar, and Chandra Kanta Mohapatra
(Rutgers University, USA; California Institute of Technology, USA; IIT Bombay, India)
Publisher's Version
Set-Multilinear and Non-commutative Formula Lower Bounds for Iterated Matrix Multiplication
Sébastien Tavenas ORCID logo, Nutan Limaye ORCID logo, and Srikanth Srinivasan ORCID logo
(Université Grenoble Alpes, France; Université Savoie Mont Blanc, France; CNRS, France; LAMA, France; IT University of Copenhagen, Denmark; Aarhus University, Denmark)
Publisher's Version
Combinatorics via Closed Orbits: Number Theoretic Ramanujan Graphs Are Not Unique Neighbor Expanders
Amitay Kamber ORCID logo and Tali Kaufman
(University of Cambridge, UK; Bar-Ilan University, Israel)
Publisher's Version
On the Complexity of CSP-Based Ideal Membership Problems
Andrei A. BulatovORCID logo and Akbar Rafiey ORCID logo
(Simon Fraser University, Canada)
Publisher's Version

Session 3B

Near-Optimal Distributed Degree+1 Coloring
Magnús M. Halldórsson ORCID logo, Fabian Kuhn ORCID logo, Alexandre Nolin ORCID logo, and Tigran Tonoyan ORCID logo
(Reykjavik University, Iceland; University of Freiburg, Germany; Krisp Technologies, Armenia)
Publisher's Version
Distributed ∆-Coloring Plays Hide-and-Seek
Alkida Balliu, Sebastian Brandt, Fabian Kuhn ORCID logo, and Dennis Olivetti
(Gran Sasso Science Institute, Italy; CISPA, Germany; University of Freiburg, Germany)
Publisher's Version
Undirected (1+𝜀)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel and Distributed Algorithms
Václav Rozhoň, Christoph Grunau ORCID logo, Bernhard Haeupler ORCID logo, Goran Zuzic ORCID logo, and Jason Li
(ETH Zurich, Switzerland; Carnegie Mellon University, USA; University of California at Berkeley, USA)
Publisher's Version
Improved Communication Complexity of Fault-Tolerant Consensus
Mohammad T. Hajiaghayi, Dariusz R. Kowalski, and Jan Olkowski
(University of Maryland, USA; Augusta University, USA)
Publisher's Version
Byzantine Agreement in Polynomial Time with Near-Optimal Resilience
Shang-En Huang ORCID logo, Seth PettieORCID logo, and Leqi ZhuORCID logo
(University of Michigan, USA)
Publisher's Version

Session 3C

No Self-Concordant Barrier Interior Point Method Is Strongly Polynomial
Xavier Allamigeon ORCID logo, Stéphane Gaubert ORCID logo, and Nicolas Vandame
(Inria, France; École Polytechnique, France; CNRS, France)
Publisher's Version
Improved Iteration Complexities for Overconstrained p-Norm Regression
Arun Jambulapati, Yang P. LiuORCID logo, and Aaron Sidford ORCID logo
(Stanford University, USA)
Publisher's Version
Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers
Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee ORCID logo, Yang P. LiuORCID logo, Richard Peng, and Aaron Sidford ORCID logo
(Simons Institute for the Theory of Computing Berkeley, USA; University of California at Berkeley, USA; Georgia Institute of Technology, USA; Stanford University, USA; University of Washington, USA)
Publisher's Version
Sparsified Block Elimination for Directed Laplacians
Richard Peng and Zhuoqing Song ORCID logo
(University of Waterloo, Canada; Fudan University, China)
Publisher's Version
Matrix Anti-concentration Inequalities with Applications
Zipei Nie ORCID logo
(Huawei, France)
Publisher's Version

Session 4A

Circuits Resilient to Short-Circuit Errors
Klim Efremenko ORCID logo, Bernhard Haeupler ORCID logo, Yael Tauman Kalai, Pritish Kamath, Gillat Kol ORCID logo, Nicolas Resch, and Raghuvansh R. Saxena ORCID logo
(Ben-Gurion University of the Negev, Israel; ETH Zurich, Switzerland; Carnegie Mellon University, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA; Google Research, USA; Princeton University, USA; CWI, Netherlands)
Publisher's Version
Explicit Binary Tree Codes with Sub-logarithmic Size Alphabet
Inbar Ben Yaacov ORCID logo, Gil CohenORCID logo, and Tal Yankovitz ORCID logo
(Tel Aviv University, Israel)
Publisher's Version
Interactive Error Correcting Codes over Binary Erasure Channels Resilient to > ½ Adversarial Corruption
Meghal Gupta ORCID logo, Yael Tauman Kalai, and Rachel Yun Zhang ORCID logo
(Microsoft Research, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
The Query Complexity of Certification
Guy Blanc, Caleb Koch, Jane Lange ORCID logo, and Li-Yang Tan ORCID logo
(Stanford University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version

Session 4B

Matrix Discrepancy from Quantum Communication
Samuel B. HopkinsORCID logo, Prasad RaghavendraORCID logo, and Abhishek Shetty
(Massachusetts Institute of Technology, USA; University of California at Berkeley, USA)
Publisher's Version
A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent
Daniel Dadush, Haotian Jiang, and Victor Reis
(CWI, Netherlands; University of Washington, USA)
Publisher's Version
Uniform Approximations for Randomized Hadamard Transforms with Applications
Yeshwanth Cherapanamjeri ORCID logo and Jelani Nelson
(University of California at Berkeley, USA)
Publisher's Version
Testing Thresholds for High-Dimensional Sparse 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, USA; Stanford University, USA)
Publisher's Version
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder Than Random
Venkatesan Guruswami, Pravesh K. Kothari ORCID logo, and Peter Manohar ORCID logo
(University of California at Berkeley, USA; Carnegie Mellon University, USA)
Publisher's Version

Session 4C

On the Hardness of Dominant Strategy Mechanism Design
Shahar Dobzinski, Shiri Ron, and Jan Vondrák
(Weizmann Institute of Science, Israel; Stanford University, USA)
Publisher's Version
Computing Simple Mechanisms: Lift-and-Round over Marginal Reduced Forms
Yang Cai ORCID logo, Argyris Oikonomou ORCID logo, and Mingfei Zhao ORCID logo
(Yale University, USA; Google Research, USA)
Publisher's Version
Approximately Efficient Bilateral Trade
Yuan DengORCID logo, Jieming MaoORCID logo, Balasubramanian SivanORCID logo, and Kangning WangORCID logo
(Google Research, USA; Duke University, USA)
Publisher's Version
Pricing Ordered Items
Shuchi Chawla ORCID logo, Rojin Rezvan ORCID logo, Yifeng Teng ORCID logo, and Christos Tzamos ORCID logo
(University of Texas at Austin, USA; Google Research, USA; University of Wisconsin-Madison, USA)
Publisher's Version
Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-player General-Sum Games
Ioannis Anagnostides, Constantinos Daskalakis ORCID logo, Gabriele Farina, Maxwell Fishelson, Noah GolowichORCID logo, and Tuomas Sandholm
(Carnegie Mellon University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version

Session 5A

Hamiltonian Complexity in the Thermodynamic Limit
Dorit Aharonov ORCID logo and Sandy Irani
(Hebrew University of Jerusalem, Israel; University of California at Irvine, USA)
Publisher's Version Info
Computational Complexity of the Ground State Energy Density Problem
James D. Watson ORCID logo and Toby S. CubittORCID logo
(University College London, UK)
Publisher's Version
Optimizing Strongly Interacting Fermionic Hamiltonians
Matthew B. Hastings and Ryan O'Donnell
(Microsoft, USA; Carnegie Mellon University, USA)
Publisher's Version
Public-Key Quantum Money with a Classical Bank
Omri Shmueli
(Tel Aviv University, Israel)
Publisher's Version
Quantum Garbled Circuits
Zvika Brakerski ORCID logo and Henry YuenORCID logo
(Weizmann Institute of Science, Israel; Columbia University, USA)
Publisher's Version

Session 5B

Reproducibility in Learning
Russell Impagliazzo ORCID logo, Rex Lei ORCID logo, Toniann Pitassi ORCID logo, and Jessica Sorrell
(University of California at San Diego, USA; Columbia University, USA)
Publisher's Version
Kalman Filtering with Adversarial Corruptions
Sitan Chen ORCID logo, Frederic Koehler, Ankur Moitra ORCID logo, and Morris Yau
(University of California at Berkeley, USA; Stanford University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games
Constantinos Daskalakis ORCID logo and Noah GolowichORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
Binary Perceptron: Efficient Algorithms Can Find Solutions in a Rare Well-Connected Cluster
Emmanuel Abbe, Shuangping Li, and Allan Sly
(EPFL, Switzerland; Princeton University, USA)
Publisher's Version
Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
Ilias Diakonikolas ORCID logo, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos ORCID logo, and Nikos Zarifis ORCID logo
(University of Wisconsin-Madison, USA; University of California at San Diego, USA)
Publisher's Version

Session 5C

Fast FPT-Approximation of Branchwidth
Fedor V. Fomin ORCID logo and Tuukka KorhonenORCID logo
(University of Bergen, Norway)
Publisher's Version
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion
Bart M. P. JansenORCID logo and Michał WłodarczykORCID logo
(Eindhoven University of Technology, Netherlands)
Publisher's Version
Fixed-Parameter Tractability of Graph Isomorphism in Graphs with an Excluded Minor
Daniel Lokshtanov ORCID logo, Marcin PilipczukORCID logo, Michał Pilipczuk ORCID logo, and Saket Saurabh
(University of California at Santa Barbara, USA; University of Warsaw, Poland; IMSc, India; University of Bergen, Norway)
Publisher's Version
Twin-Width IV: Ordered Graphs and Matrices
Édouard Bonnet ORCID logo, Ugo Giocanti, Patrice Ossona de Mendez ORCID logo, Pierre Simon ORCID logo, Stéphan Thomassé ORCID logo, and Szymon Toruńczyk ORCID logo
(LIP, France; ENS Lyon, France; CAMS, France; CNRS, France; University of California at Berkeley, USA; University of Warsaw, Poland)
Publisher's Version
Directed Flow-Augmentation
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, and Magnus Wahlström
(Université Paris-Dauphine, France; PSL Research University, France; CNRS, France; Humboldt University of Berlin, Germany; University of Warsaw, Poland; Royal Holloway University of London, UK)
Publisher's Version

Award Papers Session II: Best Student Papers

The Optimal Error Resilience of Interactive Communication over Binary Channels
Meghal Gupta ORCID logo and Rachel Yun Zhang ORCID logo
(Microsoft Research, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity
Zhiyuan Fan ORCID logo, Jiatu LiORCID logo, and Tianqi YangORCID logo
(Tsinghua University, China)
Publisher's Version

Session 6A

On Approximability of Satisfiable k-CSPs: I
Amey Bhangale ORCID logo, Subhash Khot ORCID logo, and Dor Minzer ORCID logo
(University of California at Riverside, USA; New York University, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
A Characterization of Approximability for Biased CSPs
Euiwoong Lee ORCID logo and Suprovat Ghoshal
(University of Michigan, USA)
Publisher's Version
Parallel Repetition for All 3-Player Games over Binary Alphabet
Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz ORCID logo, and Wei Zhan ORCID logo
(Princeton University, USA; NTT Research, USA)
Publisher's Version
Constant Inapproximability for PPA
Argyrios Deligkas ORCID logo, John Fearnley ORCID logo, Alexandros Hollender ORCID logo, and Themistoklis Melissourgos ORCID logo
(Royal Holloway University of London, UK; University of Liverpool, UK; University of Oxford, UK; University of Essex, UK)
Publisher's Version
Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number
Andrei A. BulatovORCID logo and Amirhossein Kazeminia ORCID logo
(Simon Fraser University, Canada)
Publisher's Version

Session 6B

Towards Optimal Lower Bounds for k-Median and k-Means Coresets
Vincent Cohen-Addad ORCID logo, Kasper Green Larsen, David SaulpicORCID logo, and Chris Schwiegelshohn
(Google Research, Switzerland; Aarhus University, Denmark; Sorbonne University, France)
Publisher's Version
Deterministic, Near-Linear 𝜀-Approximation Algorithm for Geometric Bipartite Matching
Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra, and Allen Xiao
(Duke University, USA; Dartmouth College, USA; Virginia Tech, USA)
Publisher's Version
Locality-Sensitive Orderings and Applications to Reliable Spanners
Arnold FiltserORCID logo and Hung LeORCID logo
(Bar-Ilan University, Israel; University of Massachusetts at Amherst, USA)
Publisher's Version
Nearly Optimal Vertex Fault-Tolerant Spanners in Optimal Time: Sequential, Distributed, and Parallel
Merav Parter
(Weizmann Institute of Science, Israel)
Publisher's Version
Maintaining Exact Distances under Multiple Edge Failures
Ran Duan and Hanlin RenORCID logo
(Tsinghua University, China; University of Oxford, UK)
Publisher's Version

Session 6C

Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
Karl Bringmann, Alejandro Cassis, Nick Fischer ORCID logo, and Vasileios Nakos
(Saarland University, Germany; MPI-INF, Germany; RelationalAI, USA)
Publisher's Version
Edge Sampling and Graph Parameter Estimation via Vertex Neighborhood Accesses
Jakub Tětek and Mikkel Thorup
(University of Copenhagen, Denmark)
Publisher's Version
Low-Rank Approximation with 1/𝜖1/3 Matrix-Vector Products
Ainesh Bakshi, Kenneth L. Clarkson, and David P. Woodruff ORCID logo
(Carnegie Mellon University, USA; IBM Research, USA)
Publisher's Version
Sublinear Time Spectral Density Estimation
Vladimir Braverman, Aditya Krishnan, and Christopher Musco
(Johns Hopkins University, USA; New York University, USA)
Publisher's Version
Memory Bounds for the Experts Problem
Vaidehi Srinivas, David P. Woodruff ORCID logo, Ziyu Xu, and Samson ZhouORCID logo
(Northwestern University, USA; Carnegie Mellon University, USA)
Publisher's Version

Session 7A

A Strong Version of Cobham’s Theorem
Philipp Hieronymi and Christian Schulz
(University of Bonn, Germany; University of Illinois at Urbana-Champaign, USA)
Publisher's Version
3.1no(n) Circuit Lower Bounds for Explicit Functions
Jiatu LiORCID logo and Tianqi YangORCID logo
(Tsinghua University, China)
Publisher's Version
The Approximate Degree of DNF and CNF Formulas
Alexander A. Sherstov ORCID logo
(University of California at Los Angeles, USA)
Publisher's Version
Verifying the Unseen: Interactive Proofs for Label-Invariant Distribution Properties
Tal Herman ORCID logo and Guy N. RothblumORCID logo
(Weizmann Institute of Science, Israel)
Publisher's Version
Randomized Communication and Implicit Graph Representations
Nathaniel HarmsORCID logo, Sebastian WildORCID logo, and Viktor ZamaraevORCID logo
(University of Waterloo, Canada; University of Liverpool, UK)
Publisher's Version

Session 7B

Robustly Learning Mixtures of k Arbitrary Gaussians
Ainesh Bakshi, Ilias Diakonikolas ORCID logo, He Jia, Daniel M. Kane, Pravesh K. Kothari ORCID logo, and Santosh S. Vempala
(Carnegie Mellon University, USA; University of Wisconsin-Madison, USA; Georgia Institute of Technology, USA; University of California at San Diego, USA)
Publisher's Version
Clustering Mixtures with Almost Optimal Separation in Polynomial Time
Allen Liu ORCID logo and Jerry Li ORCID logo
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)
Publisher's Version
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation
Ilias Diakonikolas ORCID logo, Daniel M. Kane ORCID logo, Daniel Kongsgaard, Jerry Li ORCID logo, and Kevin Tian
(University of Wisconsin-Madison, USA; University of California at San Diego, USA; Microsoft Research, USA; Stanford University, USA)
Publisher's Version
List-Decodable Covariance Estimation
Misha Ivkov and Pravesh K. Kothari ORCID logo
(Carnegie Mellon University, USA)
Publisher's Version

Session 7C

On the Optimal Time/Space Tradeoff for Hash Tables
Michael A. Bender ORCID logo, Martín Farach-Colton ORCID logo, John Kuszmaul, William Kuszmaul ORCID logo, and Mingmou LiuORCID logo
(Stony Brook University, USA; Rutgers University, USA; Yale University, USA; Massachusetts Institute of Technology, USA; Nanyang Technological University, Singapore)
Publisher's Version
An Extendable Data Structure for Incremental Stable Perfect Hashing
Ioana Oriana BerceaORCID logo and Guy Even ORCID logo
(IT University of Copenhagen, Denmark; Tel Aviv University, Israel)
Publisher's Version
Almost-Linear ε-Emulators for Planar Graphs
Hsien-Chih Chang, Robert Krauthgamer ORCID logo, and Zihan TanORCID logo
(Dartmouth College, USA; Weizmann Institute of Science, Israel; University of Chicago, USA)
Publisher's Version
Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality
Bernhard Haeupler ORCID logo, Harald Räcke ORCID logo, and Mohsen Ghaffari
(Carnegie Mellon University, USA; ETH Zurich, Switzerland; TU Munich, Germany)
Publisher's Version
Optimal Oblivious Reconfigurable Networks
Daniel AmirORCID logo, Tegan Wilson ORCID logo, Vishal ShrivastavORCID logo, Hakim WeatherspoonORCID logo, Robert KleinbergORCID logo, and Rachit AgarwalORCID logo
(Cornell University, USA; Purdue University, USA)
Publisher's Version

Session 8A

Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead
Noga Ron-Zewi ORCID logo and Ron D. Rothblum ORCID logo
(University of Haifa, Israel; Technion, Israel)
Publisher's Version
Rate One-Third Non-malleable Codes
Divesh Aggarwal, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Maciej Obremski, and Sruthi Sekar
(National University of Singapore, Singapore; IISc Bangalore, India; Microsoft Research, India; University of California at Berkeley, USA)
Publisher's Version Info
Deniable Encryption in a Quantum World
Andrea ColadangeloORCID logo, Shafi Goldwasser ORCID logo, and Umesh Vazirani
(University of California at Berkeley, USA; Simons Institute for the Theory of Computing Berkeley, USA)
Publisher's Version
On the Complexity of Two-Party Differential Privacy
Iftach Haitner, Noam Mazor, Jad Silbak, and Eliad Tsfadia
(Tel Aviv University, Israel)
Publisher's Version
Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
Samuel B. HopkinsORCID logo, Gautam KamathORCID logo, and Mahbod MajidORCID logo
(University of California at Berkeley, USA; Massachusetts Institute of Technology, USA; University of Waterloo, Canada)
Publisher's Version

Session 8B

Entropic Independence: Optimal Mixing of Down-Up Random Walks
Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong ORCID logo
(Stanford University, USA)
Publisher's Version
Simple Parallel Algorithms for Single-Site Dynamics
Hongyang Liu ORCID logo and Yitong Yin
(Nanjing University, China)
Publisher's Version
Low-Temperature Ising Dynamics with Random Initializations
Reza Gheissari and Alistair Sinclair
(University of California at Berkeley, USA)
Publisher's Version
Computational Thresholds for the Fixed-Magnetization Ising Model
Charlie Carlson, Ewan DaviesORCID logo, Alexandra Kolla, and Will PerkinsORCID logo
(University of Colorado Boulder, USA; University of California at Santa Cruz, USA; University of Illinois at Chicago, USA)
Publisher's Version
Approximate Counting and Sampling via Local Central Limit Theorems
Vishesh Jain ORCID logo, Will PerkinsORCID logo, Ashwin Sah ORCID logo, and Mehtaab Sawhney
(Stanford University, USA; University of Illinois at Chicago, USA; Massachusetts Institute of Technology, USA)
Publisher's Version

Session 8C

Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond
Amir Abboud ORCID logo, Karl Bringmann ORCID logo, Seri Khoury ORCID logo, and Or Zamir
(Weizmann Institute of Science, Israel; Saarland University, Germany; MPI-INF, Germany; University of California at Berkeley, USA; Institute for Advanced Study at Princeton, USA)
Publisher's Version
Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV
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
Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
Ce JinORCID logo and Yinzhan Xu ORCID logo
(Massachusetts Institute of Technology, USA)
Publisher's Version
Faster Min-Plus Product for Monotone Instances
Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang ORCID logo
(Tsinghua University, China; Tel Aviv University, Israel)
Publisher's Version
Counting Small Induced Subgraphs with Hereditary Properties
Jacob Focke ORCID logo and Marc Roth ORCID logo
(CISPA, Germany; University of Oxford, UK)
Publisher's Version

Session 9A

Pseudodeterminism: Promises and Lowerbounds
Peter Dixon, A. Pavan, Jason Vander Woude, and N. V. Vinodchandran
(Ben-Gurion University of the Negev, Israel; Iowa State University, USA; University of Nebraska-Lincoln, USA)
Publisher's Version
Worst-Case to Average-Case Reductions via Additive Combinatorics
Vahid R. Asadi ORCID logo, Alexander Golovnev ORCID logo, Tom Gur ORCID logo, and Igor Shinkar ORCID logo
(University of Waterloo, Canada; Georgetown University, USA; University of Warwick, UK; Simon Fraser University, Canada)
Publisher's Version
Robustness of Average-Case Meta-Complexity via Pseudorandomness
Rahul IlangoORCID logo, Hanlin RenORCID logo, and Rahul Santhanam
(Massachusetts Institute of Technology, USA; Oxford University, UK)
Publisher's Version
Extractors for Sum of Two Sources
Eshan Chattopadhyay ORCID logo and Jyun-Jie Liao ORCID logo
(Cornell University, USA)
Publisher's Version

Session 9B

Breaching the 2-Approximation Barrier for the Forest Augmentation Problem
Fabrizio GrandoniORCID logo, Afrouz Jabal Ameli, and Vera Traub
(USI-SUPSI, Switzerland; ETH Zurich, Switzerland)
Publisher's Version
An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-subgraph Problem
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, and Xinzhi Zhang ORCID logo
(University of Washington, USA)
Publisher's Version
Improved Approximations for Euclidean k-Means and k-Median, via Nested Quasi-Independent Sets
Vincent Cohen-Addad ORCID logo, Hossein Esfandiari, Vahab Mirrokni, and Shyam NarayananORCID logo
(Google Research, Switzerland; Google Research, USA; Massachusetts Institute of Technology, USA)
Publisher's Version
Explainable k-Means: Don’t Be Greedy, Plant Bigger Trees!
Konstantin Makarychev ORCID logo and Liren ShanORCID logo
(Northwestern University, USA)
Publisher's Version

Session 9C

Subquadratic Dynamic Path Reporting in Directed Graphs against an Adaptive Adversary
Adam Karczmarz ORCID logo, Anish Mukherjee ORCID logo, and Piotr Sankowski ORCID logo
(University of Warsaw, Poland; IDEAS NCBR, Poland)
Publisher's Version
Dynamic Suffix Array with Polylogarithmic Queries and Updates
Dominik Kempa ORCID logo and Tomasz KociumakaORCID logo
(Stony Brook University, USA; University of California at Berkeley, USA)
Publisher's Version
Dynamic Algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds
Amos Beimel ORCID logo, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol SaranurakORCID logo, and Uri Stemmer
(Ben-Gurion University of the Negev, Israel; Tel Aviv University, Israel; Google Research, Israel; Georgetown University, USA; University of Michigan, USA)
Publisher's Version
On the Complexity of Dynamic Submodular Maximization
Xi Chen and Binghui Peng ORCID logo
(Columbia University, USA)
Publisher's Version

proc time: 29.07