STOC 2021
53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)
Powered by
Conference Publishing Consulting
53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), June 21–25, 2021, Virtual, Italy

STOC 2021 – Proceedings

 Contents - Abstracts - Authors

Frontmatter

Title Page


Welcome from the Program Chair


STOC 2021 Conference Organization


Invited Presentations

Keynote

Computational Thinking in Programming Language and Compiler Design (Keynote)
Alfred V. Aho
(Columbia University, USA)


 Publisher's Version

Invited Talk

Climbing Algorithms (Invited Talk)
Leonid A. Levin
(Boston University, USA)


 Publisher's Version

Invited Papers

A Polynomial-Time Approximation Algorithm for Counting Words Accepted by an NFA (Invited Paper)
Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros
(PUC, Chile; IMFD, Chile; Carnegie Mellon University, USA)


 Publisher's Version
Chasing Convex Bodies with Linear Competitive Ratio (Invited Paper)
C. J. Argue, Anupam Gupta, Guru Guruganesh, and Ziye Tang
(Carnegie Mellon University, USA; Google Research, USA)


 Publisher's Version
Neural Tangent Kernel: Convergence and Generalization in Neural Networks (Invited Paper)
Arthur Jacot, Franck Gabriel, and Clément Hongler
(EPFL, Switzerland)


 Publisher's Version
Simplicity Creates Inequity: Implications for Fairness, Stereotypes, and Interpretability (Invited Paper)
Jon Kleinberg and Sendhil Mullainathan
(Cornell University, USA; University of Chicago, USA)


 Publisher's Version
The Ghost in the Radiation: Robust Encodings of the Black Hole Interior (Invited Paper)
Isaac H. Kim, Eugene Tang, and John Preskill
(University of Sydney, Australia; California Institute of Technology, USA)


 Publisher's Version
A New Analysis of Differential Privacy’s Generalization Guarantees (Invited Paper)
Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Moshe Shenfeld
(University of Pennsylvania, USA; Hebrew University of Jerusalem, Israel)


 Publisher's Version
Load Balancing Guardrails: Keeping Your Heavy Traffic on the Road to Low Response Times (Invited Paper)
Isaac Grosof, Ziv Scully, and Mor Harchol-Balter
(Carnegie Mellon University, USA)


 Publisher's Version
Learnability Can Be Independent of Set Theory (Invited Paper)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, and Amir Yehudayoff
(University of Waterloo, Canada; Czech Academy of Sciences, Czechia; Technion, Israel; Tel Aviv University, Israel)


 Publisher's Version

Tutorials

Log-Concave Polynomials in Theory and Applications (Tutorial)
Nima Anari and Cynthia Vinzant
(Stanford University, USA; North Carolina State University, USA; University of Washington, USA)


 Publisher's Version
Statistical Physics of Random CSPs (Tutorial)
Nike Sun
(Massachusetts Institute of Technology, USA)


 Publisher's Version

Papers

Best Student Papers

Discrepancy Minimization via a Self-Balancing Walk
Ryan Alweiss, Yang P. Liu, and Mehtaab Sawhney
(Princeton University, USA; Stanford University, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
Separating Words and Trace Reconstruction
Zachary Chase
(University of Oxford, UK)


 Publisher's Version

Best Papers

A (Slightly) Improved Approximation Algorithm for Metric TSP
Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan
(University of Washington, USA)


 Publisher's Version
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS
John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani
(University of Liverpool, UK; University of Oxford, UK)


 Publisher's Version
Indistinguishability Obfuscation from Well-Founded Assumptions
Aayush Jain, Huijia Lin, and Amit Sahai
(University of California at Los Angeles, USA; University of Washington, USA)


 Publisher's Version

Session 1A

Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design
Yufei Ruan, Jiaqi Yang, and Yuan Zhou
(University of Illinois at Urbana-Champaign, USA; Tsinghua University, China)


 Publisher's Version
Efficiently Learning Halfspaces with Tsybakov Noise
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis
(University of Wisconsin-Madison, USA; University of California at San Diego, USA)


 Publisher's Version
Robust Linear Regression: Optimal Rates in Polynomial Time
Ainesh Bakshi and Adarsh Prasad
(Carnegie Mellon University, USA)


 Publisher's Version
Statistical Query Complexity of Manifold Estimation
Eddie Aamari and Alexander Knop
(LPSM, France; Sorbonne University, France; University of Paris, France; CNRS, France; University of California at San Diego, USA)


 Publisher's Version
When Is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?
Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar
(Boston University, USA; Apple, USA)


 Publisher's Version

Session 2A

Sample-Optimal and Efficient Learning of Tree Ising Models
Constantinos Daskalakis and Qinxuan Pan
(Massachusetts Institute of Technology, USA)


 Publisher's Version
Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu
Arnab Bhattacharyya, Sutanu Gayen, Eric Price, and N. V. Vinodchandran
(National University of Singapore, Singapore; University of Texas at Austin, USA; University of Nebraska-Lincoln, USA)


 Publisher's Version
Learning Ising Models from One or Multiple Samples
Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Anthimos Vardis Kandiros
(Massachusetts Institute of Technology, USA; Google, USA)


 Publisher's Version
A New Coreset Framework for Clustering
Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn
(Google, Switzerland; Sorbonne University, France; CNRS, France; LIP6, France; Aarhus University, Denmark)


 Publisher's Version
Sample-Efficient Proper PAC Learning with Approximate Differential Privacy
Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi
(Google Research, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version

Session 1B

Log-Rank and Lifting for AND-Functions
Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan
(University of California at San Diego, USA; Tsinghua University, China)


 Publisher's Version
Automating Algebraic Proof Systems Is NP-Hard
Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, and Dmitry Sokolov
(Czech Academy of Sciences, Czechia; EPFL, Switzerland; University of Copenhagen, Denmark; Lund University, Sweden; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA; McGill University, Canada; St. Petersburg State University, Russia; Russian Academy of Sciences, Russia)


 Publisher's Version
Strong Co-nondeterministic Lower Bounds for NP Cannot Be Proved Feasibly
Ján Pich and Rahul Santhanam
(Czech Academy of Sciences, Czechia; University of Oxford, UK)


 Publisher's Version
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity
Rahul Santhanam and Iddo Tzameret
(University of Oxford, UK; Imperial College London, UK)


 Publisher's Version
New Separations Results for External Information
Mark Braverman and Dor Minzer
(Princeton University, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version

Session 2B

Polynomial Time Deterministic Identity Testing Algorithm for Σ[3]ΠΣΠ[2] Circuits via Edelstein–Kelly Type Theorem for Quadratic Polynomials
Shir Peleg and Amir Shpilka
(Tel Aviv University, Israel)


 Publisher's Version
An Improved Derandomization of the Switching Lemma
Zander Kelley
(University of Illinois at Urbana-Champaign, USA)


 Publisher's Version
Simple and Fast Derandomization from Very Hard Functions: Eliminating Randomness at Almost No Cost
Lijie Chen and Roei Tell
(Massachusetts Institute of Technology, USA)


 Publisher's Version
Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions
Shuichi Hirahara
(National Institute of Informatics, Japan)


 Publisher's Version
Pseudodeterministic Algorithms and the Structure of Probabilistic Time
Zhenjian Lu, Igor C. Oliveira, and Rahul Santhanam
(University of Warwick, UK; University of Oxford, UK)


 Publisher's Version

Session 1C

Vertex Connectivity in Poly-logarithmic Max-Flows
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai
(Carnegie Mellon University, USA; University of Copenhagen, Denmark; KTH, Sweden; Duke University, USA; University of Michigan, USA; Aalto University, Finland)


 Publisher's Version
Finding Large Induced Sparse Subgraphs in C>t -Free Graphs in Quasipolynomial Time
Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski
(University of California at Santa Barbara, USA; University of Warsaw, Poland; Warsaw University of Technology, Poland)


 Publisher's Version
Clan Embeddings into Trees, and Low Treewidth Graphs
Arnold Filtser and Hung Le
(Columbia University, USA; University of Massachusetts, USA)


 Publisher's Version
Tree Embeddings for Hop-Constrained Network Design
Bernhard Haeupler, D. Ellis Hershkowitz, and Goran Zuzic
(Carnegie Mellon University, USA; ETH Zurich, Switzerland)


 Publisher's Version
Bridging the Gap between Tree and Connectivity Augmentation: Unified and Stronger Approaches
Federica Cecchetto, Vera Traub, and Rico Zenklusen
(ETH Zurich, Switzerland)


 Publisher's Version

Session 2C

Deterministic Mincut in Almost-Linear Time
Jason Li
(Carnegie Mellon University, USA)


 Publisher's Version
Support of Closed Walks and Second Eigenvalue Multiplicity of Graphs
Theo McKenzie, Peter Michael Reichstein Rasmussen, and Nikhil Srivastava
(University of California at Berkeley, USA; University of Copenhagen, Denmark)


 Publisher's Version
Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, and Thuy-Duong Vuong
(Stanford University, USA; University of Washington, USA; North Carolina State University, USA)


 Publisher's Version
Breaking the Quadratic Barrier for Matroid Intersection
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, and Danupon Nanongkai
(KTH, Sweden; University of Copenhagen, Denmark)


 Publisher's Version
Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More
Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, and Thuy-Duong Vuong
(Stanford University, USA)


 Publisher's Version

Session 3A

Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev
(Princeton University, USA; Tel Aviv University, Israel; Harvard University, USA; Massachusetts Institute of Technology, USA; Technion, Israel; Google Research, Israel; Weizmann Institute of Science, Israel; Boston University, USA)


 Publisher's Version
Stronger Calibration Lower Bounds via Sidestepping
Mingda Qiao and Gregory Valiant
(Stanford University, USA)


 Publisher's Version
Hardness of Learning DNFs using Halfspaces
Suprovat Ghoshal and Rishi Saket
(University of Michigan, USA; IBM Research, India)


 Publisher's Version
Boosting Simple Learners
Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran
(Princeton University, USA; Tel Aviv University, Israel; OrCam, Israel; Google AI, USA; Technion, Israel; Google Research, Israel)


 Publisher's Version
Algorithmic Foundations for the Diffraction Limit
Sitan Chen and Ankur Moitra
(Massachusetts Institute of Technology, USA)


 Publisher's Version

Session 4A

VC Dimension and Distribution-Free Sample-Based Testing
Eric Blais, Renato Ferreira Pinto Jr., and Nathaniel Harms
(University of Waterloo, Canada; Google, Canada)


 Publisher's Version
Settling the Robust Learnability of Mixtures of Gaussians
Allen Liu and Ankur Moitra
(Massachusetts Institute of Technology, USA)


 Publisher's Version
A Theory of Universal Learning
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff
(Google, Switzerland; Toyota Technological Institute at Chicago, USA; Technion, Israel; Google Research, Israel; Princeton University, USA)


 Publisher's Version
Optimal Testing of Discrete Distributions with High Probability
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, and Eric Price
(University of Wisconsin-Madison, USA; MPI-INF, Germany; University of California at San Diego, USA; Princeton University, USA; University of Texas at Austin, USA)


 Publisher's Version

Session 3B

Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon
Seth Pettie and Dingyu Wang
(University of Michigan, USA)


 Publisher's Version
Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu
(Massachusetts Institute of Technology, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)


 Publisher's Version
Robust Testing of Low Dimensional Functions
Anindya De, Elchanan Mossel, and Joe Neeman
(University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; University of Texas at Austin, USA)


 Publisher's Version
Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida
(EPFL, Switzerland; Weizmann Institute of Science, Israel; National Institute of Informatics, Japan)


 Publisher's Version
Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma
Sepehr Assadi and Vishvajeet N
(Rutgers University, USA)


 Publisher's Version

Session 4B

Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time
Julia Chuzhoy
(Toyota Technological Institute at Chicago, USA)


 Publisher's Version
Improved Dynamic Algorithms for Longest Increasing Subsequence
Tomasz Kociumaka and Saeed Seddighin
(University of California at Berkeley, USA; Toyota Technological Institute at Chicago, USA)


 Publisher's Version
Fully Dynamic Approximation of LIS in Polylogarithmic Time
Paweł Gawrychowski and Wojciech Janczewski
(University of Wrocław, Poland)


 Publisher's Version
A Framework for Dynamic Matching in Weighted Graphs
Aaron Bernstein, Aditi Dudeja, and Zachary Langley
(Rutgers University, USA)


 Publisher's Version
Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program
Zhiyi Huang and Xinkai Shu
(University of Hong Kong, China)


 Publisher's Version

Session 3C

Continuous LWE
Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang
(New York University, USA; University of Michigan, USA)


 Publisher's Version
SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE
Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, and Rachel Zhang
(University of Illinois at Urbana-Champaign, USA; Microsoft Research, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version
Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
Yanyi Liu and Rafael Pass
(Cornell University, USA)


 Publisher's Version
Indistinguishability Obfuscation from Circular Security
Romain Gay and Rafael Pass
(IBM Research, Switzerland; Cornell Tech, USA)


 Publisher's Version
Fiat–Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW Is Not Zero-Knowledge)
Justin Holmgren, Alex Lombardi, and Ron D. Rothblum
(NTT Research, USA; Massachusetts Institute of Technology, USA; Technion, Israel)


 Publisher's Version

Session 4C

Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma
Lijie Chen and Xin Lyu
(Massachusetts Institute of Technology, USA; Tsinghua University, China)


 Publisher's Version
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity
Josh Alman
(Harvard University, USA)


 Publisher's Version
Lower Bounds for Monotone Arithmetic Circuits via Communication Complexity
Arkadev Chattopadhyay, Rajit Datta, and Partha Mukhopadhyay
(Tata Institute of Fundamental Research, India; Chennai Mathematical Institute, India)


 Publisher's Version
Structure vs. Randomness for Bilinear Maps
Alex Cohen and Guy Moshkovitz
(Yale University, USA; City University of New York, USA)


 Publisher's Version
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits
Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich
(Rutgers University, USA; Boston College, USA)


 Publisher's Version

Session 5A

A Faster Algorithm for Solving General LPs
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang
(Columbia University, USA; Institute for Advanced Study at Princeton, USA)


 Publisher's Version
Combinatorial Bernoulli Factories: Matchings, Flows, and Other Polytopes
Rad Niazadeh, Renato Paes Leme, and Jon Schneider
(University of Chicago, USA; Google Research, USA)


 Publisher's Version
Capacity Lower Bounds via Productization
Leonid Gurvits and Jonathan Leake
(City College of New York, USA; TU Berlin, Germany)


 Publisher's Version
Minimum Cost Flows, MDPs, and ℓ1-Regression in Nearly Linear Time for Dense Instances
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang
(KTH, Sweden; University of Washington, USA; Microsoft Research, USA; Stanford University, USA; University of Michigan, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA; Google Research, USA)


 Publisher's Version
A Framework for Quadratic Form Maximization over Convex Sets through Nonconvex Relaxations
Vijay Bhattiprolu, Euiwoong Lee, and Assaf Naor
(Institute for Advanced Study at Princeton, USA; Princeton University, USA; University of Michigan, USA)


 Publisher's Version

Session 5B

The Randomized Communication Complexity of Randomized Auctions
Aviad Rubinstein and Junyao Zhao
(Stanford University, USA)


 Publisher's Version
Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex-Nonconcave Min-Max Optimization
Oren Mangoubi and Nisheeth K. Vishnoi
(Worcester Polytechnic Institute, USA; Yale University, USA)


 Publisher's Version
Contextual Search in the Presence of Irrational Agents
Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, and Robert Schapire
(Microsoft Research, USA; Harvard University, USA)


 Publisher's Version
How Much Data Is Sufficient to Learn High-Performing Algorithms? Generalization Guarantees for Data-Driven Algorithm Design
Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik
(Carnegie Mellon University, USA; University of Texas at El Paso, USA; University of Pennsylvania, USA)


 Publisher's Version
The Communication Complexity of Payment Computation
Shahar Dobzinski and Shiri Ron
(Weizmann Institute of Science, Israel)


 Publisher's Version
Exponential Communication Separations between Notions of Selfishness
Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, and Junyao Zhao
(Stanford University, USA; Princeton University, USA)


 Publisher's Version

Session 5C

Reducing Isotropy and Volume to KLS: An O*(n3ψ2) Volume Algorithm
He Jia, Aditi Laddha, Yin Tat Lee, and Santosh Vempala
(Georgia Institute of Technology, USA; University of Washington, USA; Microsoft Research, USA)


 Publisher's Version
A New Algorithm for Euclidean Shortest Paths in the Plane
Haitao Wang
(Utah State University, USA)


 Publisher's Version
Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions
Natan Rubin
(Ben-Gurion University of the Negev, Israel)


 Publisher's Version
Dynamic Planar Point Location in Optimal Time
Yakov Nekrich
(Michigan Technological University, USA)


 Publisher's Version

Session 6A

When Is Approximate Counting for Conjunctive Queries Tractable?
Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros
(PUC, Chile; IMFD, Chile; Carnegie Mellon University, USA)


 Publisher's Version
Near-Linear Time Approximation Schemes for Steiner Tree and Forest in Low-Dimensional Spaces
Yair Bartal and Lee-Ad Gottlieb
(Hebrew University of Jerusalem, Israel; Ariel University, Israel)


 Publisher's Version
A (2 + ε)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine
Lars Rohwedder and Andreas Wiese
(EPFL, Switzerland; University of Chile, Chile)


 Publisher's Version
A Quasipolynomial (2 + ε)-Approximation for Planar Sparsest Cut
Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, and Jason Li
(Google, Switzerland; Carnegie Mellon University, USA; Brown University, USA)


 Publisher's Version
Flow Time Scheduling with Uncertain Processing Time
Yossi Azar, Stefano Leonardi, and Noam Touitou
(Tel Aviv University, Israel; Sapienza University of Rome, Italy)


 Publisher's Version

Session 7A

The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation
Albert Cheu and Jonathan Ullman
(Northeastern University, USA)


 Publisher's Version
Outcome Indistinguishability
Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona
(Harvard University, USA; University of California at Berkeley, USA; Stanford University, USA; Weizmann Institute of Science, Israel)


 Publisher's Version
Optimal Labelling Schemes for Adjacency, Comparability, and Reachability
Marthe Bonamy, Louis Esperet, Carla Groenland, and Alex Scott
(CNRS, France; Labri, France; University of Bordeaux, France; G-SCOP, France; Grenoble Alps University, France; University of Oxford, UK)


 Publisher's Version
Bipartite Perfect Matching as a Real Polynomial
Gal Beniamini and Noam Nisan
(Hebrew University of Jerusalem, Israel)


 Publisher's Version
Efficient and Near-Optimal Algorithms for Sampling Connected Subgraphs
Marco Bressan
(University of Milan, Italy)


 Publisher's Version

Session 6B

Distributed Weighted Min-Cut in Nearly-Optimal Time
Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai
(ETH Zurich, Switzerland; University of Toronto, Canada; KTH, Sweden; University of Copenhagen, Denmark)


 Publisher's Version
A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique
Krzysztof Nowicki
(University of Copenhagen, Denmark; University of Wrocław, Poland)


 Publisher's Version
Universally-Optimal Distributed Algorithms for Known Topologies
Bernhard Haeupler, David Wajc, and Goran Zuzic
(Carnegie Mellon University, USA; ETH Zurich, Switzerland; Stanford University, USA)


 Publisher's Version
Efficient Randomized Distributed Coloring in CONGEST
Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan
(Reykjavik University, Iceland; University of Freiburg, Germany; Technion, Israel)


 Publisher's Version
The Communication Complexity of Multiparty Set Disjointness under Product Distributions
Nachum Dershowitz, Rotem Oshman, and Tal Roth
(Tel Aviv University, Israel)


 Publisher's Version

Session 7B

Hop-Constrained Oblivious Routing
Mohsen Ghaffari, Bernhard Haeupler, and Goran Zuzic
(ETH Zurich, Switzerland; Carnegie Mellon University, USA)


 Publisher's Version
Efficient Randomized DCAS
George Giakkoupis, Mehrdad Jafari Giv, and Philipp Woelfel
(Inria, France; University of Rennes, France; CNRS, France; IRISA, France; University of Calgary, Canada)


 Publisher's Version
Optimal Error Resilience of Adaptive Message Exchange
Klim Efremenko, Gillat Kol, and Raghuvansh R. Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)


 Publisher's Version
How Asymmetry Helps Buffer Management: Achieving Optimal Tail Size in Cup Games
William Kuszmaul
(Massachusetts Institute of Technology, USA)


 Publisher's Version
Load Balancing with Dynamic Set of Balls and Bins
Anders Aamand, Jakob Bæk Tejs Knudsen, and Mikkel Thorup
(University of Copenhagen, Denmark)


 Publisher's Version

Session 6C

Fiber Bundle Codes: Breaking the N1/2 polylog(N) Barrier for Quantum LDPC Codes
Matthew B. Hastings, Jeongwan Haah, and Ryan O'Donnell
(Station Q, USA; Microsoft Quantum, USA; Carnegie Mellon University, USA)


 Publisher's Version
An Optimal Separation of Randomized and Quantum Query Complexity
Alexander A. Sherstov, Andrey A. Storozhenko, and Pei Wu
(University of California at Los Angeles, USA)


 Publisher's Version
k-Forrelation Optimally Separates Quantum and Classical Query Complexity
Nikhil Bansal and Makrand Sinha
(CWI, Netherlands; Eindhoven University of Technology, Netherlands)


 Publisher's Version
New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with Ω(√n logk n) Distance
Tali Kaufman and Ran J. Tessler
(Bar-Ilan University, Israel; Weizmann Institute of Science, Israel)


 Publisher's Version
Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem
Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal
(University of Texas at Austin, USA; University of Waterloo, Canada; Microsoft Quantum, USA; Microsoft Research, USA; Northwestern University, USA; University of California at Berkeley, USA)


 Publisher's Version
Eliminating Intermediate Measurements in Space-Bounded Quantum Computation
Bill Fefferman and Zachary Remscrim
(University of Chicago, USA)


 Publisher's Version

Session 7C

(Sub)Exponential Advantage of Adiabatic Quantum Computation with No Sign Problem
András Gilyén, Matthew B. Hastings, and Umesh Vazirani
(California Institute of Technology, USA; Microsoft Quantum, USA; Microsoft Research, USA; University of California at Berkeley, USA)


 Publisher's Version
Succinct Blind Quantum Computation using a Random Oracle
Jiayu Zhang
(Boston University, USA)


 Publisher's Version
Sampling Matrices from Harish-Chandra–Itzykson–Zuber Densities with Applications to Quantum Inference and Differential Privacy
Jonathan Leake, Colin McSwiggen, and Nisheeth K. Vishnoi
(TU Berlin, Germany; University of Tokyo, Japan; Yale University, USA)


 Publisher's Version
Improved Quantum Data Analysis
Costin Bădescu and Ryan O'Donnell
(Carnegie Mellon University, USA)


 Publisher's Version

Session 8A

Approximating Nash Social Welfare under Rado Valuations
Jugal Garg, Edin Husić, and László A. Végh
(University of Illinois at Urbana-Champaign, USA; London School of Economics and Political Science, UK)


 Publisher's Version
Settling the Complexity of Nash Equilibrium in Congestion Games
Yakov Babichenko and Aviad Rubinstein
(Technion, Israel; Stanford University, USA)


 Publisher's Version
Revelation Gap for Pricing from Samples
Yiding Feng, Jason D. Hartline, and Yingkai Li
(Northwestern University, USA)


 Publisher's Version
Efficient Two-Sided Markets with Limited Information
Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser
(Google Research, Switzerland; Sapienza University of Rome, Italy)


 Publisher's Version
The Complexity of Constrained Min-Max Optimization
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis
(Massachusetts Institute of Technology, USA; Singapore University of Technology and Design, Singapore; University of California at Berkeley, USA)


 Publisher's Version

Session 9A

On Codes Decoding a Constant Fraction of Errors on the BSC
Jan Hązła, Alex Samorodnitsky, and Ori Sberlo
(EPFL, Switzerland; Hebrew University of Jerusalem, Israel; Tel Aviv University, Israel)


 Publisher's Version
Decoding Multivariate Multiplicity Codes on Product Sets
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, and Madhu Sudan
(Tata Institute of Fundamental Research, India; IIT Bombay, India; Harvard University, USA)


 Publisher's Version
Efficient List-Decoding with Constant Alphabet and List Sizes
Zeyu Guo and Noga Ron-Zewi
(University of Haifa, Israel)


 Publisher's Version
Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity
Ronen Shaltiel and Jad Silbak
(University of Haifa, Israel; Tel Aviv University, Israel)


 Publisher's Version
Near-Linear Time Decoding of Ta-Shma’s Codes via Splittable Regularity
Fernando Granha Jeronimo, Shashank Srivastava, and Madhur Tulsiani
(University of Chicago, USA; Toyota Technological Institute at Chicago, USA)


 Publisher's Version

Session 8B

Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
Zongchen Chen, Kuikui Liu, and Eric Vigoda
(Georgia Institute of Technology, USA; University of Washington, USA)


 Publisher's Version
Entropy Decay in the Swendsen–Wang Dynamics on ℤd
Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair, and Eric Vigoda
(Pennsylvania State University, USA; Roma Tre University, Italy; University of California at Berkeley, USA; Georgia Institute of Technology, USA)


 Publisher's Version
Sampling Constraint Satisfaction Solutions in the Local Lemma Regime
Weiming Feng, Kun He, and Yitong Yin
(Nanjing University, China; Institute of Computing Technology at Chinese Academy of Sciences, China; University of Chinese Academy of Sciences, China)


 Publisher's Version
Frozen 1-RSB Structure of the Symmetric Ising Perceptron
Will Perkins and Changji Xu
(University of Illinois at Chicago, USA; Harvard University, USA)


 Publisher's Version
Perfectly Sampling k ≥ (8/3 + o(1))Δ-Colorings in Graphs
Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney
(Simons Institute for the Theory of Computing Berkeley, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version

Session 9B

The Metric Relaxation for 0-Extension Admits an Ω(log2/3k) Gap
Roy Schwartz and Nitzan Tur
(Technion, Israel)


 Publisher's Version
Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups
Amey Bhangale and Subhash Khot
(University of California at Riverside, USA; New York University, USA)


 Publisher's Version
Playing Unique Games on Certified Small-Set Expanders
Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, and David Steurer
(Harvard University, USA; Carnegie Mellon University, USA; Stanford University, USA; ETH Zurich, Switzerland)


 Publisher's Version
Expander Random Walks: A Fourier-Analytic Approach
Gil Cohen, Noam Peri, and Amnon Ta-Shma
(Tel Aviv University, Israel)


 Publisher's Version
Local Concentration Inequalities and Tomaszewski’s Conjecture
Nathan Keller and Ohad Klein
(Bar-Ilan University, Israel)


 Publisher's Version

Session 8C

Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors
Jesper Nederlof and Karol Węgrzycki
(Utrecht University, Netherlands; Saarland University, Germany; MPI-INF, Germany)


 Publisher's Version
Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH)
Ray Li
(Stanford University, USA)


 Publisher's Version
Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
Mina Dalirrooyfard and Nicole Wein
(Massachusetts Institute of Technology, USA)


 Publisher's Version
Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution
Karl Bringmann, Nick Fischer, and Vasileios Nakos
(Saarland University, Germany; MPI-INF, Germany)


 Publisher's Version
Subcubic Algorithms for Gomory–Hu Tree in Unweighted Graphs
Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi
(Weizmann Institute of Science, Israel)


 Publisher's Version
Approximate Gomory–Hu Tree Is Faster Than n – 1 Max-Flows
Jason Li and Debmalya Panigrahi
(Carnegie Mellon University, USA; Duke University, USA)


 Publisher's Version

Session 9C

Constant Approximating k-Clique Is W[1]-Hard
Bingkai Lin
(Nanjing University, China)


 Publisher's Version
Vertex Deletion Parameterized by Elimination Distance and Even Less
Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk
(Eindhoven University of Technology, Netherlands)


 Publisher's Version
A Full Complexity Dichotomy for Immanant Families
Radu Curticapean
(IT University of Copenhagen, Denmark)


 Publisher's Version
A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
Sally Dong, Yin Tat Lee, and Guanghao Ye
(University of Washington, USA; Microsoft Research, USA)


 Publisher's Version

proc time: 0.88