STOC 2020
52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020)
Powered by
Conference Publishing Consulting
52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), June 22–26, 2020, Chicago, IL, USA

STOC 2020 – Proceedings

 Contents - Abstracts - Authors

Frontmatter

Title Page


Article: stoc20foreword-fm000-p doi:
Welcome from the Program Chair


Article: stoc20foreword-fm001-p doi:
STOC 2020 Conference Organization


Article: stoc20foreword-fm002-p doi:
Sponsors of STOC 2020 and TheoryFest


Article: stoc20foreword-fm003-p doi:

Papers

Session 1A: TSP

An Improved Approximation Algorithm for ATSP
Vera Traub and Jens Vygen
(University of Bonn, Germany)


 Publisher's Version Article: stoc20main-p19-p doi:10.1145/3357713.3384233
Reducing Path TSP to TSP
Vera Traub, Jens Vygen, and Rico Zenklusen
(University of Bonn, Germany; ETH Zurich, Switzerland)


 Publisher's Version Article: stoc20main-p154-p doi:10.1145/3357713.3384256
An Improved Approximation Algorithm for TSP in the Half Integral Case
Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan
(University of Washington, USA)


 Publisher's Version Article: stoc20main-p255-p doi:10.1145/3357713.3384273
Bipartite TSP in O(1.9999ⁿ) Time, Assuming Quadratic Time Matrix Multiplication
Jesper Nederlof
(Utrecht University, Netherlands)


 Publisher's Version Article: stoc20main-p190-p doi:10.1145/3357713.3384264

Session 1B: Proof Complexity and Applications of Logics

Semi-algebraic Proofs, IPS Lower Bounds, and the τ-Conjecture: Can a Natural Number Be Negative?
Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, and Iddo Tzameret
(Steklov Institute of Mathematics at St. Petersburg, Russia; St. Petersburg State University, Russia; CNRS, France; University of Lille, France; Royal Holloway University of London, UK)


 Publisher's Version Article: stoc20main-p80-p doi:10.1145/3357713.3384245
Automating Cutting Planes Is NP-Hard
Mika Göös, Sajin Koroth, Ian Mertz, and Toniann Pitassi
(Stanford University, USA; Simon Fraser University, Canada; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA)


 Publisher's Version Article: stoc20main-p88-p doi:10.1145/3357713.3384248
(Semi)Algebraic Proofs over {±1} Variables
Dmitry Sokolov
(St. Petersburg State University, Russia; Steklov Institute of Mathematics at St. Petersburg, Russia)


 Publisher's Version Article: stoc20main-p353-p doi:10.1145/3357713.3384288
QCSP Monsters and the Demise of the Chen Conjecture
Dmitriy Zhuk and Barnaby Martin
(Moscow State University, Russia; Durham University, UK)


 Publisher's Version Article: stoc20main-p10-p doi:10.1145/3357713.3384232

Session 1C: Distributed and Parallel Algorithms I

Contention Resolution without Collision Detection
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, and Seth Pettie
(Stony Brook University, USA; Bar-Ilan University, Israel; Massachusetts Institute of Technology, USA; University of Michigan, USA)


 Publisher's Version Article: stoc20main-p491-p doi:10.1145/3357713.3384305
Optimal Time and Space Leader Election in Population Protocols
Petra Berenbrink, George Giakkoupis, and Peter Kling
(University of Hamburg, Germany; Inria, France; University of Rennes, France; CNRS, France; IRISA, France)


 Publisher's Version Article: stoc20main-p620-p doi:10.1145/3357713.3384312
A Lower Bound for Parallel Submodular Minimization
Eric Balkanski and Yaron Singer
(Harvard University, USA)


 Publisher's Version Article: stoc20main-p345-p doi:10.1145/3357713.3384287
A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization
Wenzheng Li, Paul Liu, and Jan Vondrák
(Stanford University, USA)


 Publisher's Version Article: stoc20main-p594-p doi:10.1145/3357713.3384311

Session 2A: Dynamic Algorithms

New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein
(University of Copenhagen, Denmark; Massachusetts Institute of Technology, USA)


 Publisher's Version Article: stoc20main-p29-p doi:10.1145/3357713.3384236
Fully-Dynamic Planarity Testing in Polylogarithmic Time
Jacob Holm and Eva Rotenberg
(University of Copenhagen, Denmark; DTU, Denmark)


 Publisher's Version Article: stoc20main-p112-p doi:10.1145/3357713.3384249
Near-Optimal Fully Dynamic Densest Subgraph
Saurabh Sawlani and Junxing Wang
(Georgia Institute of Technology, USA; Carnegie Mellon University, USA)


 Publisher's Version Article: stoc20main-p795-p doi:10.1145/3357713.3384327
Rounding Dynamic Matchings against an Adaptive Adversary
David Wajc
(Carnegie Mellon University, USA)


 Publisher's Version Article: stoc20main-p158-p doi:10.1145/3357713.3384258

Session 2B: Boolean Function Analysis and Algebraic Complexity

Concentration on the Boolean Hypercube via Pathwise Stochastic Analysis
Ronen Eldan and Renan Gross
(Weizmann Institute of Science, Israel)


 Publisher's Version Article: stoc20main-p1-p doi:10.1145/3357713.3384230
AND Testing and Robust Judgement Aggregation
Yuval Filmus, Noam Lifshitz, Dor Minzer, and Elchanan Mossel
(Technion, Israel; Hebrew University of Jerusalem, Israel; Institute for Advanced Study at Princeton, USA; Massachusetts Institute of Technology, USA)


 Publisher's Version Article: stoc20main-p150-p doi:10.1145/3357713.3384254
XOR Lemmas for Resilient Functions against Polynomials
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman
(Cornell University, USA; Ohio State University, USA; Carnegie Mellon University, USA; University of California at San Diego, USA; University of Texas at Austin, USA)


 Publisher's Version Article: stoc20main-p62-p doi:10.1145/3357713.3384242
Decision List Compression by Mild Random Restrictions
Shachar Lovett, Kewen Wu, and Jiapeng Zhang
(University of California at San Diego, USA; Peking University, China; Harvard University, USA)


 Publisher's Version Article: stoc20main-p57-p doi:10.1145/3357713.3384241

Session 2C: Cryptography

One-Shot Signatures and Applications to Hybrid Quantum/Classical Authentication
Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry
(Princeton University, USA; City University of New York, USA; University of Edinburgh, UK)


 Publisher's Version Article: stoc20main-p490-p doi:10.1145/3357713.3384304
Post-quantum Zero Knowledge in Constant Rounds
Nir Bitansky and Omri Shmueli
(Tel Aviv University, Israel)


 Publisher's Version Article: stoc20main-p761-p doi:10.1145/3357713.3384324
Better Secret Sharing via Robust Conditional Disclosure of Secrets
Benny Applebaum, Amos Beimel, Oded Nir, and Naty Peter
(Tel Aviv University, Israel; Ben-Gurion University of the Negev, Israel)


 Publisher's Version Article: stoc20main-p401-p doi:10.1145/3357713.3384293
Data Structures Meet Cryptography: 3SUM with Preprocessing
Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, and Vinod Vaikuntanathan
(Harvard University, USA; New York University Shanghai, China; Massachusetts Institute of Technology, USA)


 Publisher's Version Article: stoc20main-p1178-p doi:10.1145/3357713.3384342

Session 3A: Distributed and Parallel Algorithms II

Faster Parallel Algorithm for Approximate Shortest Path
Jason Li
(Carnegie Mellon University, USA)


 Publisher's Version Article: stoc20main-p237-p doi:10.1145/3357713.3384268
Parallel Approximate Undirected Shortest Paths via Low Hop Emulators
Alexandr Andoni, Clifford Stein, and Peilin Zhong
(Columbia University, USA)


 Publisher's Version Article: stoc20main-p747-p doi:10.1145/3357713.3384321
Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths
Nairen Cao, Jeremy T. Fineman, and Katina Russell
(Georgetown University, USA)


 Publisher's Version Article: stoc20main-p246-p doi:10.1145/3357713.3384270
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
Václav Rozhoň and Mohsen Ghaffari
(ETH Zurich, Switzerland)


 Publisher's Version Article: stoc20main-p460-p doi:10.1145/3357713.3384298
Walking Randomly, Massively, and Efficiently
Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
(Google Research, USA; Massachusetts Institute of Technology, USA; IBM Research, USA; University of Warsaw, Poland)


 Publisher's Version Article: stoc20main-p479-p doi:10.1145/3357713.3384303

Session 3B: Quantum (Inspired) Computation

Classical Algorithms, Correlation Decay, and Complex Zeros of Partition Functions of Quantum Many-Body Systems
Aram W. Harrow, Saeed Mehraban, and Mehdi Soleimanifar
(Massachusetts Institute of Technology, USA; California Institute of Technology, USA)


 Publisher's Version Article: stoc20main-p748-p doi:10.1145/3357713.3384322
Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang
(University of Texas at Austin, USA; California Institute of Technology, USA; University of Maryland, USA; University of Washington, USA)


 Publisher's Version Article: stoc20main-p633-p doi:10.1145/3357713.3384314
Bare Quantum Simultaneity versus Classical Interactivity in Communication Complexity
Dmitry Gavinsky
(Czech Academy of Sciences, Czechia)


 Publisher's Version Article: stoc20main-p70-p doi:10.1145/3357713.3384243
Quadratic Speedup for Finding Marked Vertices by Quantum Walks
Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis
(University of Latvia, Latvia; QuSoft, Netherlands; CWI, Netherlands; University of Amsterdam, Netherlands)


 Publisher's Version Article: stoc20main-p135-p doi:10.1145/3357713.3384252

Session 3C: Privacy and Fairness

The Power of Factorization Mechanisms in Local and Central Differential Privacy
Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman
(University of Toronto, Canada; Northeastern University, USA)


 Publisher's Version Article: stoc20main-p453-p doi:10.1145/3357713.3384297
Private Stochastic Convex Optimization: Optimal Rates in Linear Time
Vitaly Feldman, Tomer Koren, and Kunal Talwar
(Google Research, USA; Tel Aviv University, Israel; Google, Israel)


 Publisher's Version Article: stoc20main-p873-p doi:10.1145/3357713.3384335
Interaction Is Necessary for Distributed Learning with Privacy or Communication Constraints
Yuval Dagan and Vitaly Feldman
(Massachusetts Institute of Technology, USA; Google Research, USA)


 Publisher's Version Article: stoc20main-p646-p doi:10.1145/3357713.3384315
Approximately Stable Committee Selection
Zhihao Jiang, Kamesh Munagala, and Kangning Wang
(Tsinghua University, China; Duke University, USA)


 Publisher's Version Article: stoc20main-p35-p doi:10.1145/3357713.3384238

Session 4A: Graph Theory and Algorithms

The Karger-Stein Algorithm Is Optimal for k-Cut
Anupam Gupta, Euiwoong Lee, and Jason Li
(Carnegie Mellon University, USA; New York University, USA)


 Publisher's Version Article: stoc20main-p338-p doi:10.1145/3357713.3384285
A Phase Transition and a Quadratic Time Unbiased Estimator for Network Reliability
David R. Karger
(Massachusetts Institute of Technology, USA)


 Publisher's Version Article: stoc20main-p916-p doi:10.1145/3357713.3384336
Weighted Min-Cut: Sequential, Cut-Query, and Streaming Algorithms
Sagnik Mukhopadhyay and Danupon Nanongkai
(KTH, Sweden)


 Publisher's Version Article: stoc20main-p857-p doi:10.1145/3357713.3384334
Explicit Near-Ramanujan Graphs of Every Degree
Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes
(University of California at Berkeley, USA; Carnegie Mellon University, USA)


 Publisher's Version Article: stoc20main-p9-p doi:10.1145/3357713.3384231

Session 4B: Coding and Information Theory

Optimally Resilient Codes for List-Decoding from Insertions and Deletions
Venkatesan Guruswami, Bernhard Haeupler, and Amirbehshad Shahrasbi
(Carnegie Mellon University, USA)


 Publisher's Version Article: stoc20main-p178-p doi:10.1145/3357713.3384262
Combinatorial List-Decoding of Reed-Solomon Codes beyond the Johnson Radius
Chong Shangguan and Itzhak Tamo
(Tel Aviv University, Israel)


 Publisher's Version Article: stoc20main-p419-p doi:10.1145/3357713.3384295
Arikan Meets Shannon: Polar Codes with Near-Optimal Convergence to Channel Capacity
Venkatesan Guruswami, Andrii Riazanov, and Min Ye
(Carnegie Mellon University, USA; Tsinghua-Berkeley Shenzhen Institute, China)