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 – Preliminary Table of Contents

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)
Article Search
Reducing Path TSP to TSP
Vera Traub, Jens Vygen, and Rico Zenklusen
(University of Bonn, Germany; ETH Zurich, Switzerland)
Article Search
An Improved Approximation Algorithm for TSP in the Half Integral Case
Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan
(University of Washington, USA)
Article Search
Bipartite TSP in O(1.9999ⁿ) Time, Assuming Quadratic Time Matrix Multiplication
Jesper Nederlof
(Utrecht University, Netherlands)
Article Search

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)
Article Search
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)
Preprint
(Semi)Algebraic Proofs over {±1} Variables
Dmitry Sokolov
(St. Petersburg State University, Russia; Steklov Institute of Mathematics at St. Petersburg, Russia)
Article Search
QCSP Monsters and the Demise of the Chen Conjecture
Dmitriy Zhuk and Barnaby Martin
(Moscow State University, Russia; Durham University, UK)
Article Search

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)
Article Search
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)
Article Search
A Lower Bound for Parallel Submodular Minimization
Eric Balkanski and Yaron Singer
(Harvard University, USA)
Article Search
A Polynomial Lower Bound on Adaptive Complexity of Submodular Maximization
Wenzheng Li, Paul Liu, and Jan Vondrák
(Stanford University, USA)
Article Search

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)
Article Search
Fully-Dynamic Planarity Testing in Polylogarithmic Time
Jacob Holm and Eva Rotenberg
(University of Copenhagen, Denmark; DTU, Denmark)
Preprint
Near-Optimal Fully Dynamic Densest Subgraph
Saurabh Sawlani and Junxing Wang
(Georgia Institute of Technology, USA; Carnegie Mellon University, USA)
Article Search
Rounding Dynamic Matchings against an Adaptive Adversary
David Wajc
(Carnegie Mellon University, USA)
Article Search

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)
Preprint
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)
Article Search
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)
Article Search
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)
Article Search

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)
Article Search
Post-quantum Zero Knowledge in Constant Rounds
Nir Bitansky and Omri Shmueli
(Tel Aviv University, Israel)
Article Search
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)
Article Search
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)
Preprint

Session 3A: Distributed and Parallel Algorithms II

Faster Parallel Algorithm for Approximate Shortest Path
Jason Li
(Carnegie Mellon University, USA)
Article Search
Parallel Approximate Undirected Shortest Paths via Low Hop Emulators
Alexandr Andoni, Clifford Stein, and Peilin Zhong
(Columbia University, USA)
Preprint
Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths
Nairen Cao, Jeremy T. Fineman, and Katina Russell
(Georgetown University, USA)
Article Search
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
Václav Rozhoň and Mohsen Ghaffari
(ETH Zurich, Switzerland)
Preprint
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)
Article Search

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)
Preprint
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)
Article Search
Bare Quantum Simultaneity versus Classical Interactivity in Communication Complexity
Dmitry Gavinsky
(Czech Academy of Sciences, Czechia)
Preprint
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)
Preprint

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)
Preprint
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)
Article Search
Interaction Is Necessary for Distributed Learning with Privacy or Communication Constraints
Yuval Dagan and Vitaly Feldman
(Massachusetts Institute of Technology, USA; Google Research, USA)
Article Search
Approximately Stable Committee Selection
Zhihao Jiang, Kamesh Munagala, and Kangning Wang
(Tsinghua University, China; Duke University, USA)
Article Search

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)
Article Search
A Phase Transition and a Quadratic Time Unbiased Estimator for Network Reliability
David R. Karger
(Massachusetts Institute of Technology, USA)
Article Search
Weighted Min-Cut: Sequential, Cut-Query, and Streaming Algorithms
Sagnik Mukhopadhyay and Danupon Nanongkai
(KTH, Sweden)
Preprint
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)
Preprint

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)
Preprint
Combinatorial List-Decoding of Reed-Solomon Codes beyond the Johnson Radius
Chong Shangguan and Itzhak Tamo
(Tel Aviv University, Israel)
Preprint
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)
Preprint
Interactive Error Resilience beyond 2/7
Klim Efremenko, Gillat Kol, and Raghuvansh R. Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)
Article Search

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)
Preprint
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)
Article Search
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)
Article Search
Testing Noisy Linear Functions for Sparsity
Xue Chen, Anindya De, and Rocco A. Servedio
(Northwestern University, USA; University of Pennsylvania, USA; Columbia University, USA)
Preprint

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)
Article Search

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)
Article Search

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)
Article Search
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)
Article Search
Dynamic Algorithms for LIS and Distance to Monotonicity
Michael Mitzenmacher and Saeed Seddighin
(Harvard University, USA)
Article Search
Constant-Factor Approximation of Near-Linear Edit Distance in Near-Linear Time
Joshua Brakensiek and Aviad Rubinstein
(Stanford University, USA)
Article Search
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)
Article Search

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)
Article Search
The Program-Size Complexity of Self-Assembled Paths
Pierre-Étienne Meunier, Damien Regnault, and Damien Woods
(Maynooth University, Irland; University of Évry, France; University of Paris-Saclay, France)
Preprint
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)
Article Search
Catalytic Approaches to the Tree Evaluation Problem
James Cook and Ian Mertz
(University of Toronto, Canada)
Article Search

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)
Article Search
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)
Preprint
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)
Article Search
Faster Energy Maximization for Faster Maximum Flow
Yang P. Liu and Aaron Sidford
(Stanford University, USA)
Preprint

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)
Article Search
A Spectral Approach to Network Design
Lap Chi Lau and Hong Zhou
(University of Waterloo, Canada)
Article Search
Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4
Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu
(University of California at Berkeley, USA)
Article Search
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)
Article Search

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)
Article Search
Interactive Shallow Clifford Circuits: Quantum Advantage against NC¹ and Beyond
Daniel Grier and Luke Schaeffer
(University of Waterloo, Canada)
Article Search
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)
Article Search
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)
Article Search
The Impossibility of Efficient Quantum Weak Coin Flipping
Carl A. Miller
(NIST, USA; University of Maryland, USA)
Preprint

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)
Preprint
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)
Preprint
Does Learning Require Memorization? A Short Tale about a Long Tail
Vitaly Feldman
(Google Research, USA)
Article Search Video Info
Efficiently Learning Structured Distributions from Untrusted Batches
Sitan Chen, Jerry Li, and Ankur Moitra
(Massachusetts Institute of Technology, USA; Microsoft Research, USA)
Article Search

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)
Article Search
Top-𝑘-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
Karl Bringmann and Vasileios Nakos
(Saarland University, Germany; MPI-INF, Germany)
Article Search
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)
Article Search
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)
Preprint

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)
Article Search
Unexpected Hardness Results for Kolmogorov Complexity under Uniform Reductions
Shuichi Hirahara
(National Institute of Informatics, Japan)
Article Search
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)
Article Search
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)
Article Search

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)
Article Search
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)
Article Search
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)
Article Search
Stochastic Matching with Few Queries: (1-ε) Approximation
Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi
(University of Maryland, USA)
Article Search

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)
Article Search
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)
Article Search
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue
Zhiyi Huang and Qiankun Zhang
(University of Hong Kong, China)
Article Search
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)
Article Search

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)
Article Search
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)
Preprint
Improved Analysis of Higher Order Random Walks and Applications
Vedat Levi Alev and Lap Chi Lau
(University of Waterloo, Canada)
Article Search
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)
Article Search

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)
Article Search
Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-armed Bandits
Sepehr Assadi and Chen Wang
(Rutgers University, USA)
Article Search
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)
Preprint
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)
Article Search

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)
Article Search
Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time
Jesper Nederlof
(Utrecht University, Netherlands)
Article Search
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)
Article Search
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)
Preprint

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)
Article Search
Sharp Threshold Results for Computational Complexity
Lijie Chen, Ce Jin, and R. Ryan Williams
(Massachusetts Institute of Technology, USA; Tsinghua University, China)
Article Search
A Robust Version of Hegedus’s Lemma, with Applications
Srikanth Srinivasan
(IIT Bombay, India)
Article Search
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)
Article Search

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)
Article Search
Nearly Optimal Static Las Vegas Succinct Dictionary
Huacheng Yu
(Princeton University, USA)
Article Search
Lower Bound for Succinct Range Minimum Query
Mingmou Liu and Huacheng Yu
(Nanjing University, China; Princeton University, USA)
Preprint
Coresets for Clustering in Euclidean Spaces: Importance Sampling Is Nearly Optimal
Lingxiao Huang and Nisheeth K. Vishnoi
(Yale University, USA)
Preprint

proc time: 9.46