STOC 2020
52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020)

Powered by

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

Welcome from the Program Chair

STOC 2020 Conference Organization

Sponsors of STOC 2020 and TheoryFest

Papers

Session 1A: TSP

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

Publisher's Version

Reducing Path TSP to TSP
Vera Traub, Jens Vygen, and Rico Zenklusen
(University of Bonn, Germany; ETH Zurich, Switzerland)

Publisher's Version

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

Bipartite TSP in O(1.9999ⁿ) Time, Assuming Quadratic Time Matrix Multiplication
Jesper Nederlof
(Utrecht University, Netherlands)

Publisher's Version

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

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

(Semi)Algebraic Proofs over {±1} Variables
Dmitry Sokolov
(St. Petersburg State University, Russia; Steklov Institute of Mathematics at St. Petersburg, Russia)

Publisher's Version

QCSP Monsters and the Demise of the Chen Conjecture
Dmitriy Zhuk and Barnaby Martin
(Moscow State University, Russia; Durham University, UK)

Publisher's Version

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

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

A Lower Bound for Parallel Submodular Minimization
Eric Balkanski and Yaron Singer
(Harvard University, USA)

Publisher's Version

A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization
Wenzheng Li, Paul Liu, and Jan Vondrák
(Stanford University, USA)

Publisher's Version

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

Fully-Dynamic Planarity Testing in Polylogarithmic Time
Jacob Holm and Eva Rotenberg
(University of Copenhagen, Denmark; DTU, Denmark)

Publisher's Version

Near-Optimal Fully Dynamic Densest Subgraph
Saurabh Sawlani and Junxing Wang
(Georgia Institute of Technology, USA; Carnegie Mellon University, USA)

Publisher's Version

Rounding Dynamic Matchings against an Adaptive Adversary
David Wajc
(Carnegie Mellon University, USA)

Publisher's Version

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

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

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

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

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

Post-quantum Zero Knowledge in Constant Rounds
Nir Bitansky and Omri Shmueli
(Tel Aviv University, Israel)

Publisher's Version

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

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

Session 3A: Distributed and Parallel Algorithms II

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

Publisher's Version

Parallel Approximate Undirected Shortest Paths via Low Hop Emulators
Alexandr Andoni, Clifford Stein, and Peilin Zhong
(Columbia University, USA)

Publisher's Version

Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths
Nairen Cao, Jeremy T. Fineman, and Katina Russell
(Georgetown University, USA)

Publisher's Version

Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
Václav Rozhoň and Mohsen Ghaffari
(ETH Zurich, Switzerland)

Publisher's Version

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

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

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

Bare Quantum Simultaneity versus Classical Interactivity in Communication Complexity
Dmitry Gavinsky
(Czech Academy of Sciences, Czechia)

Publisher's Version

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

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

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

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

Approximately Stable Committee Selection
Zhihao Jiang, Kamesh Munagala, and Kangning Wang
(Tsinghua University, China; Duke University, USA)

Publisher's Version

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

A Phase Transition and a Quadratic Time Unbiased Estimator for Network Reliability
David R. Karger
(Massachusetts Institute of Technology, USA)

Publisher's Version

Weighted Min-Cut: Sequential, Cut-Query, and Streaming Algorithms
Sagnik Mukhopadhyay and Danupon Nanongkai
(KTH, Sweden)

Publisher's Version

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

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

Combinatorial List-Decoding of Reed-Solomon Codes beyond the Johnson Radius
Chong Shangguan and Itzhak Tamo
(Tel Aviv University, Israel)

Publisher's Version

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)

Publisher's Version

Interactive Error Resilience beyond 2/7
Klim Efremenko, Gillat Kol, and Raghuvansh R. Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)

Publisher's Version

Session 4C: Learning and Testing

Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
Rong Ge, Holden Lee, and Jianfeng Lu
(Duke University, USA)

Publisher's Version

Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
Sitan Chen, Jerry Li, and Zhao Song
(Massachusetts Institute of Technology, USA; Microsoft Research, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)

Publisher's Version

Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, and Nilesh Tripuraneni
(University of California at Berkeley, USA)

Publisher's Version

Testing Noisy Linear Functions for Sparsity
Xue Chen, Anindya De, and Rocco A. Servedio
(Northwestern University, USA; University of Pennsylvania, USA; Columbia University, USA)

Publisher's Version

Session 5A: Best Paper

Improved Bounds for the Sunflower Lemma
Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang
(Princeton University, USA; University of California at San Diego, USA; Peking University, China; Harvard University, USA)

Publisher's Version

Session 5B: Best Student Paper

Improved Bounds for Perfect Sampling of k-Colorings in Graphs
Siddharth Bhandari and Sayantan Chakraborty
(Tata Institute of Fundamental Research, India)

Publisher's Version

Session 6A: Strings and Sequences

Approximating Text-to-Pattern Hamming Distances
Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat
(University of Illinois at Urbana-Champaign, USA; Bar-Ilan University, Israel)

Publisher's Version

Does Preprocessing Help in Fast Sequence Comparisons?
Elazar Goldenberg, Aviad Rubinstein, and Barna Saha
(Academic College of Tel Aviv-Yaffo, Israel; Stanford University, USA; University of California at Berkeley, USA)

Publisher's Version

Dynamic Algorithms for LIS and Distance to Monotonicity
Michael Mitzenmacher and Saeed Seddighin
(Harvard University, USA)

Publisher's Version

Constant-Factor Approximation of Near-Linear Edit Distance in Near-Linear Time
Joshua Brakensiek and Aviad Rubinstein
(Stanford University, USA)

Publisher's Version

Constant Factor Approximations to Edit Distance on Far Input Pairs in Nearly Linear Time
Michal Koucký and Michael Saks
(Charles University in Prague, Czechia; Rutgers University, USA)

Publisher's Version

Session 6B: Complexity I

Implementing Geometric Complexity Theory: On the Separation of Orbit Closures via Symmetries
Christian Ikenmeyer and Umangathan Kandasamy
(University of Liverpool, UK; Saarland University, Germany)

Publisher's Version

The Program-Size Complexity of Self-Assembled Paths
Pierre-Étienne Meunier, Damien Regnault, and Damien Woods
(Maynooth University, Ireland; University of Évry, France; University of Paris-Saclay, France)

Publisher's Version

Efficient Sampling and Counting Algorithms for the Potts Model on ℤᵈ at All Temperatures
Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, and Prasad Tetali
(University of California at Berkeley, USA; University of Bristol, UK; University of Illinois at Chicago, USA; Georgia Institute of Technology, USA)

Publisher's Version

Catalytic Approaches to the Tree Evaluation Problem
James Cook and Ian Mertz
(University of Toronto, Canada)

Publisher's Version

Session 6C: Optimization

A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix
Daniel Dadush, Sophie Huiberts, Bento Natura, and László A. Végh
(CWI, Netherlands; London School of Economics and Political Science, UK)

Publisher's Version

Solving Tall Dense Linear Programs in Nearly Linear Time
Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song
(KTH, Sweden; University of Washington, USA; Microsoft Research, USA; Stanford University, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)

Publisher's Version

Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian
(Stanford University, USA; University of Washington, USA; Microsoft Research, USA)

Publisher's Version

Faster Energy Maximization for Faster Maximum Flow
Yang P. Liu and Aaron Sidford
(Stanford University, USA)

Publisher's Version

Session 7A: Approximation Algorithms

Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
Jarosław Byrka, Fabrizio Grandoni, and Afrouz Jabal Ameli
(University of Wrocław, Poland; IDSIA, Switzerland)

Publisher's Version

A Spectral Approach to Network Design
Lap Chi Lau and Hong Zhou
(University of Waterloo, Canada)

Publisher's Version

Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4
Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu
(University of California at Berkeley, USA)

Publisher's Version

Fast Sampling and Counting 𝑘-SAT Solutions in the Local Lemma Regime
Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang
(Nanjing University, China; University of Edinburgh, UK; Shanghai Jiao Tong University, China)

Publisher's Version

Session 7B: Quantum Computation

Entanglement Subvolume Law for 2D Frustration-Free Spin Systems
Anurag Anshu, Itai Arad, and David Gosset
(University of Waterloo, Canada; Perimeter Institute for Theoretical Physics, Canada; Technion, Israel)

Publisher's Version

Interactive Shallow Clifford Circuits: Quantum Advantage against NC¹ and Beyond
Daniel Grier and Luke Schaeffer
(University of Waterloo, Canada)

Publisher's Version

Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
Matthew Coudron and Sanketh Menda
(University of Waterloo, Canada; University of Maryland, USA; NIST, USA)

Publisher's Version

On the Need for Large Quantum Depth
Nai-Hui Chia, Kai-Min Chung, and Ching-Yi Lai
(University of Texas at Austin, USA; Academia Sinica, Taiwan; National Chiao Tung University, Taiwan)

Publisher's Version

The Impossibility of Efficient Quantum Weak Coin Flipping
Carl A. Miller
(NIST, USA; University of Maryland, USA)

Publisher's Version

Session 7C: Continuous Optimization / Machine Learning

On the Computability of Continuous Maximum Entropy Distributions with Applications
Jonathan Leake and Nisheeth K. Vishnoi
(KTH, Sweden; Yale University, USA)

Publisher's Version

An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games, and Its Applications
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong
(University of Washington, USA; Microsoft Research, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)

Publisher's Version

Does Learning Require Memorization? A Short Tale about a Long Tail
Vitaly Feldman
(Google Research, USA)

Publisher's Version

Efficiently Learning Structured Distributions from Untrusted Batches
Sitan Chen, Jerry Li, and Ankur Moitra
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)

Publisher's Version

Session 8A: Fine-Grained Complexity

All Non-trivial Variants of 3-LDT Are Equivalent
Bartłomiej Dudek, Paweł Gawrychowski, and Tatiana Starikovskaya
(University of Wrocław, Poland; PSL University, France)

Publisher's Version

Top-𝑘-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
Karl Bringmann and Vasileios Nakos
(Saarland University, Germany; MPI-INF, Germany)

Publisher's Version

New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut
Amir Abboud, Vincent Cohen-Addad, and Philip N. Klein
(IBM, USA; CNRS, France; UPMC, France; Brown University, USA)

Publisher's Version

Constant Girth Approximation for Directed Graphs in Subquadratic Time
Shiri Chechik, Yang P. Liu, Omer Rotem, and Aaron Sidford
(Tel Aviv University, Israel; Stanford University, USA)

Publisher's Version

Session 8B: Complexity Theory II

Non-signaling Proofs with O(√ log n) Provers Are in PSPACE
Dhiraj Holden and Yael Tauman Kalai
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)

Publisher's Version

Unexpected Hardness Results for Kolmogorov Complexity under Uniform Reductions
Shuichi Hirahara
(National Institute of Informatics, Japan)

Publisher's Version

Smoothed Complexity of Local Max-Cut and Binary Max-CSP
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, and Xinzhi Zhang
(Columbia University, USA; Tsinghua University, China)

Publisher's Version

How to Lose at Monte Carlo: A Simple Dynamical System Whose Typical Statistical Behavior Is Non-computable
Cristobal Rojas and Michael Yampolsky
(Andrés Bello National University, Chile; University of Toronto, Canada)

Publisher's Version

Session 8C: Algorithmic Game Theory and Matchings

Separating the Communication Complexity of Truthful and Non-truthful Combinatorial Auctions
Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, and S. Matthew Weinberg
(Rutgers University, USA; Princeton University, USA)

Publisher's Version

On the Nisan-Ronen Conjecture for Submodular Valuations
George Christodoulou, Elias Koutsoupias, and Annamária Kovács
(University of Liverpool, UK; University of Oxford, UK; Goethe University Frankfurt, Germany)

Publisher's Version

Towards a Better Understanding of Randomized Greedy Matching
Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang
(Shanghai University of Finance and Economics, China; University of Macau, China; University of Hong Kong, China)

Publisher's Version

Stochastic Matching with Few Queries: (1-ε) Approximation
Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi
(University of Maryland, USA)

Publisher's Version

Session 9A: Online Algorithms

Caching with Time Windows
Anupam Gupta, Amit Kumar, and Debmalya Panigrahi
(Carnegie Mellon University, USA; IIT Delhi, India; Duke University, USA)

Publisher's Version

Online Vector Balancing and Geometric Discrepancy
Nikhil Bansal, Haotian Jiang, Sahil Singla, and Makrand Sinha
(Eindhoven University of Technology, Netherlands; CWI, Netherlands; University of Washington, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)

Publisher's Version

Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue
Zhiyi Huang and Qiankun Zhang
(University of Hong Kong, China)

Publisher's Version

Unbounded Lower Bound for k-Server against Weak Adversaries
Marcin Bienkowski, Jarosław Byrka, Christian Coester, and Łukasz Jeż
(University of Wrocław, Poland; CWI, Netherlands)

Publisher's Version

Session 9B: Randomness in Computing

Fooling Gaussian PTFs via Local Hyperconcentration
Ryan O'Donnell, Rocco A. Servedio, and Li-Yang Tan
(Carnegie Mellon University, USA; Columbia University, USA; Stanford University, USA)

Publisher's Version

Extractors for Adversarial Sources via Extremal Hypergraphs
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, and Xin Li
(Cornell University, USA; Carnegie Mellon University, USA; Johns Hopkins University, USA)

Publisher's Version

Improved Analysis of Higher Order Random Walks and Applications
Vedat Levi Alev and Lap Chi Lau
(University of Waterloo, Canada)

Publisher's Version

Strong Self-Concordance and Sampling
Aditi Laddha, Yin Tat Lee, and Santosh Vempala
(Georgia Institute of Technology, USA; University of Washington, USA; Microsoft Research, USA)

Publisher's Version

Session 9C: Streaming, Sketching, and Big Data

Separations and Equivalences between Turnstile Streaming and Linear Sketching
John Kallaugher and Eric Price
(University of Texas at Austin, USA)

Publisher's Version

Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-armed Bandits
Sepehr Assadi and Chen Wang
(Rutgers University, USA)

Publisher's Version

Non-adaptive Adaptive Sampling on Turnstile Streams
Sepideh Mahabadi, Ilya Razenshteyn, David P. Woodruff, and Samson Zhou
(Toyota Technological Institute at Chicago, USA; Microsoft Research, USA; Carnegie Mellon University, USA)

Publisher's Version

Fast Hashing with Strong Concentration Bounds
Anders Aamand, Jakob Bæk Tejs Knudsen, Mathias Bæk Tejs Knudsen, Peter Michael Reichstein Rasmussen, and Mikkel Thorup
(University of Copenhagen, Denmark; SupWiz, Denmark)

Publisher's Version

Session 10A: Graph Theory and Fixed-Parameter Tractability

Three-in-a-Tree in Near Linear Time
Kai-Yuan Lai, Hsueh-I Lu, and Mikkel Thorup
(National Taiwan University, Taiwan; University of Copenhagen, Denmark)

Publisher's Version

Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time
Jesper Nederlof
(Utrecht University, Netherlands)

Publisher's Version

An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
Daniel Lokshtanov, Pranabendu Misra, Michał Pilipczuk, Saket Saurabh, and Meirav Zehavi
(University of California at Santa Barbara, USA; MPI-INF, Germany; University of Warsaw, Poland; IMSc, India; Ben-Gurion University of the Negev, Israel)

Publisher's Version

Hitting Topological Minors Is FPT
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi
(University of Bergen, Norway; University of California at Santa Barbara, USA; IIT Hyderabad, India; IMSc, India; Ben-Gurion University of the Negev, Israel)

Publisher's Version

Session 10B: Complexity Theory III

Strong Average-Case Lower Bounds from Non-trivial Derandomization
Lijie Chen and Hanlin Ren
(Massachusetts Institute of Technology, USA; Tsinghua University, China)

Publisher's Version

Sharp Threshold Results for Computational Complexity
Lijie Chen, Ce Jin, and R. Ryan Williams
(Massachusetts Institute of Technology, USA; Tsinghua University, China)

Publisher's Version

A Robust Version of Hegedus’s Lemma, with Applications
Srikanth Srinivasan
(IIT Bombay, India)

Publisher's Version

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen
(University of Haifa, Israel; Google Research, Switzerland; EPFL, Switzerland; ETH Zurich, Switzerland)

Publisher's Version

Session 10C: Data Structures / Big Data

Distance Sensitivity Oracles with Subcubic Preprocessing Time and Fast Query Time
Shiri Chechik and Sarel Cohen
(Tel Aviv University, Israel)

Publisher's Version

Nearly Optimal Static Las Vegas Succinct Dictionary
Huacheng Yu
(Princeton University, USA)

Publisher's Version

Lower Bound for Succinct Range Minimum Query
Mingmou Liu and Huacheng Yu
(Nanjing University, China; Princeton University, USA)

Publisher's Version

Coresets for Clustering in Euclidean Spaces: Importance Sampling Is Nearly Optimal
Lingxiao Huang and Nisheeth K. Vishnoi
(Yale University, USA)

Publisher's Version

proc time: 0.87