The times listed in this table are in Universal Coordinated Time.
Note: While most time zones observe daylight saving (summer) time, UTC does not. Please take this into account when you compute the offset between your time zone and UTC.
Note: Session start times are fixed; individual talk times are not. A talk may start earlier or later than shown, depending on when the previous talk ends.
STOC 2020 Program
  Monday, June 22
 
Session 1A (stream)
Chair: Marek Cygan
Session 1B (stream)
Chair: Rafael Oliveira
Session 1C (stream)
Chair: Pravesh Kothari
15:00
An improved approximation algorithm for ATSP (video)
Vera Traub (University of Bonn), Jens Vygen (University of Bonn)
Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative? (video)
Yaroslav Alekseev (Steklov Institute of Mathematics at St. Petersburg, and Chebyshev Laboratory at St. Petersburg State University), Dima Grigoriev (CNRS, Mathematiques, Universite de Lille), Edward A. Hirsch (Steklov Institute of Mathematics at St. Petersburg), Iddo Tzameret (Royal Holloway, University of London)
Contention Resolution without Collision Detection (video)
Michael A. Bender (Stony Brook University), Tsvi Kopelowitz (Bar-Ilan University), William Kuszmaul (MIT), Seth Pettie (University of Michigan)
15:10
Reducing Path TSP to TSP (video)
Vera Traub (University of Bonn), Jens Vygen (University of Bonn), Rico Zenklusen (ETH Zurich)
Automating Cutting Planes is NP-Hard (video)
Mika Goos (Stanford University), Sajin Koroth (Simon Fraser University), Ian Mertz (University of Toronto), Toniann Pitassi (University of Toronto and IAS)
Optimal Time and Space Leader Election in Population Protocols (video)
Petra Berenbrink (University of Hamburg), George Giakkoupis (INRIA), Peter Kling (University of Hamburg)
15:20
An Improved Approximation Algorithm for TSP in the Half Integral Case (video)
Anna R. Karlin (University of Washington), Nathan Klein (University of Washington), Shayan Oveis Gharan (University of Washington)
(Semi)Algebraic Proofs over $\{\pm 1\}$ Variables (video)
Dmitry Sokolov (Lund University, University of Copenhagen)
A Lower Bound for Parallel Submodular Minimization (video)
Eric Balkanski (Harvard University), Yaron Singer (Harvard University)
15:30
Bipartite TSP in $O(1.9999^n)$ Time, Assuming Quadratic Time Matrix Multiplication (video)
Jesper Nederlof (Utrecht University)
QCSP monsters and the demise of the Chen Conjecture (video)
Dmitriy Zhuk (Lomonosov Moscow State University), Barnaby Martin (Durham University)
A polynomial lower bound on adaptive complexity of submodular maximization (video)
Wenzheng Li (Stanford), Paul Liu (Stanford), Jan Vondrak (Stanford)
15:40 Break
17:00
Workshop 1: New Frontiers in Approximate Counting (stream)
Organizers: Heng Guo (University of Edinburgh), Jingcheng Liu (Caltech)
Workshop 2: MCSP and Hardness Magnification (stream)
Organizers: Josh Alman (Harvard), Marco Carmosino (Simon Fraser), Ryan Williams (MIT)
20:00 Break
 
Session 2A (stream)
Chair: Thatchaphol Saranurak
Session 2B (stream)
Chair: Sofya Raskhodnikova
Session 2C (stream)
Chair: Dakshita Khurana
21:00
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs (video)
Maximilian Probst (Department of Computer Science, University of Copenhagen), Virginia Vassilevska Williams (Massachusetts Institute of Technology), Nicole Wein (MIT)
Concentration on the Boolean hypercube via pathwise stochastic analysis (video)
Ronen Eldan (Weizmann Institute of Science), Renan Gross (Weizmann Institute of Science)
One-shot Signatures and Applications to Hybrid Quantum/Classical Authentication (video)
Ryan Amos (Princeton University), Marios Georgiou (City University of New York), Aggelos Kiayias (University of Edinburgh), Mark Zhandry (Princeton University)
21:10
Fully-dynamic Planarity Testing in Polylogarithmic Time (video)
Jacob Holm (University of Copenhagen), Eva Rotenberg (Technical University of Denmark)
AND Testing and Robust Judgement Aggregation (video)
Yuval Filmus (Technion), Noam Lifshitz (Hebrew University), Dor Minzer (Institute of Advanced Study), Elchanan Mossel (MIT)
Post-Quantum Zero Knowledge in Constant Rounds (video)
Omri Shmueli (Tel Aviv University), Nir Bitansky (Tel Aviv University)
21:20
Near-Optimal Fully Dynamic Densest Subgraph (video)
Saurabh Sawlani (Georgia Institute of Technology), Junxing Wang (Carnegie Mellon University)
XOR Lemmas for Resilient Functions Against Polynomials (video)
Eshan Chattopadhyay (Cornell University), Pooya Hatami (Ohio State University), Kaave Hosseini (Carnegie Mellon University), Shachar Lovett (UCSD), David Zuckerman (University of Texas at Austin)
Better Secret Sharing via Robust Conditional Disclosure of Secrets (video)
Benny Applebaum (Tel-Aviv University), Amos Beimel (Ben-Gurion University of the Negev), Oded Nir (Tel-Aviv University), Naty Peter (Ben-Gurion University of the Negev)
21:30
Rounding Dynamic Matchings Against an Adaptive Adversary (video)
David Wajc (Carnegie Mellon University)
Decision list compression by mild random restrictions (video)
Shachar Lovett (UCSD), Kewen Wu (Peking University), Jiapeng Zhang (Harvard University)
Data Structures Meet Cryptography: 3SUM with Preprocessing (video)
Alexander Golovnev (Harvard University), Siyao Guo (NYU Shanghai), Thibaut Horel (MIT), Sunoo Park (MIT & Harvard), Vinod Vaikuntanathan (MIT)
  Tuesday, June 23
 
Session 3A (stream)
Chair: Chandra Chekuri
Session 3B (stream)
Chair: Boaz Barak
Session 3C (stream)
Chair: Mark Bun
15:00
Faster Parallel Algorithm for Approximate Shortest Path (video)
Jason Li (Carnegie Mellon University)

Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators (video)
Alexandr Andoni (Columbia University), Clifford Stein (Columbia University), Peilin Zhong (Columbia University)
Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems (video)
Aram Harrow (MIT), Saeed Mehraban (Caltech), Mehdi Soleimanifar (MIT)
The Power of Factorization Mechanisms in Local and Central Differential Privacy (video)
Alexander Edmonds (University of Toronto), Aleksandar Nikolov (University of Toronto), Jonathan Ullman (Northeastern University)
15:10
Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths (video)
Nairen Cao (Georgetown University), Jeremy Fineman (Georgetown University), Katina Russell (Georgetown University)
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning (video)
Nai-Hui Chia (University of Texas at Austin), Andras Gilyen (IQIM, Caltech), Tongyang Li (University of Maryland), Han-Hsuan Lin (University of Texas at Austin), Ewin Tang (University of Washington), Chunhao Wang (University of Texas at Austin)
Private Stochastic Convex Optimization: Optimal Rates in Linear Time (video)
Vitaly Feldman (Google Research), Tomer Koren (Google Research), Kunal Talwar (Google Research)
15:20
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization (video)
Vaclav Rozhon (ETH Zurich), Mohsen Ghaffari (ETH Zurich)
Bare quantum simultaneity versus classical interactivity in communication complexity (video)
Dmitry Gavinsky (Institute of Mathematics of the Czech Academy of Sciences)
Interaction is necessary for distributed learning with privacy or communication constraints (video)
Yuval Dagan (MIT), Vitaly Feldman (Google Research)
15:30
Walking Randomly, Massively, and Efficiently (video)
Jakub Łącki (Google Research, New York), Slobodan Mitrović (MIT), Krzysztof Onak (IBM Research), Piotr Sankowski (University of Warsaw, Poland)
Quadratic speedup for finding marked vertices by quantum walks (video)
Andris Ambainis (University of Latvia), Andras Gilyen (IQIM, Caltech), Stacey Jeffery (CWI), Martins Kokainis (University of Latvia)
Approximately Stable Committee Selection (video)
Zhihao Jiang (Tsinghua University), Kamesh Munagala (Duke University), Kangning Wang (Duke University)
15:40 Break
16:00 Junior/Senior Lunch
17:00
Workshop 3: Recent Advances in Discrepancy and Applications (stream)
Organizers: Nikhil Bansal (Eindhoven University), Aleksandar Nikolov (University of Toronto)
20:00 Break
 
Session 4A (stream)
Chair: Sanjeev Khanna
Session 4B (stream)
Chair: Noga Ron-Zewi
Session 4C (stream)
Chair: Dana Ron
21:00
The Karger-Stein Algorithm is Optimal for k-cut (video)
Anupam Gupta (Carnegie Mellon University), Euiwoong Lee (New York University), Jason Li (Carnegie Mellon University)
Optimally Resilient Codes for List-Decoding from Insertions and Deletions (video)
Venkatesan Guruswami (Carnegie Mellon University), Bernhard Haeupler (Carnegie Mellon University), Amirbehshad Shahrasbi (Carnegie Mellon University)
Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds (video)
Rong Ge (Duke University), Holden Lee (Duke University), Jianfeng Lu (Duke University)
21:10
A Phase Transition and Quadratic Time Estimator for Network Reliability (video)
David Karger (MIT)
Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius (video)
Chong Shangguan (Tel Aviv University), Itzhak Tamo (Tel Aviv University)
Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments (video)
Sitan Chen (MIT), Jerry Li (Microsoft Research), Zhao Song (UT Austin)
21:20
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms (video)
Sagnik Mukhopadhyay (KTH Royal Institute of Technology), Danupon Nanongkai (KTH Royal Institute of Technology)
Arikan meets Shannon: Polar codes with near-optimal convergence to channel capacity (video)
Venkatesan Guruswami (Carnegie Mellon University), Andrii Riazanov (Carnegie Mellon University), Min Ye (Tsinghua-Berkeley Shenzhen Institute)
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond (video)
Yeshwanth Cherapanamjeri (UC Berkeley), Sam Hopkins (UC Berkeley), Tarun Kathuria (UC Berkeley), Prasad Raghavendra (UC Berkeley), Nilesh Tripuraneni (UC Berkeley)
21:30
Explicit near-Ramanujan graphs of every degree (video)
Sidhanth Mohanty (University of California Berkeley), Ryan O'Donnell (Carnegie Mellon University), Pedro Paredes (Carnegie Mellon University)
Interactive Error Resilience Beyond $\frac{2}{7}$ (video)
Klim Efremenko (Ben-Gurion University), Gillat Kol (Princeton University), Raghuvansh R. Saxena (Princeton University)
Testing noisy linear functions for sparsity (video)
Xue Chen (Northwestern University), Anindya De (University of Pennsylvania), Rocco A. Servedio (Columbia University)
  Wednesday, June 24
 
Session 5 (stream)
Chair: Madhur Tulsiani
15:00
Ryan Alweiss (Princeton University), Shachar Lovett (UCSD), Kewen Wu (Peking University), Jiapeng Zhang (Harvard University)
15:20
Siddharth Bhandari (Tata Institute of Fundamental Research, Mumbai), Sayantan Chakraborty (Tata Institute of Fundamental Research, Mumbai)
15:40 Break
16:00 Business Meeting
18:00 Social Event: Virtual Gather.town Meeting
20:00 Break
 
Session 6A (stream)
Chair: Yevgeniy Dodis
Session 6B (stream)
Chair: Rafael Oliveira
Session 6C (stream)
Chair: Omri Weinstein
21:00
Approximating Text-to-Pattern Hamming Distances (video)
Timothy M. Chan (UIUC), Shay Golan (Bar-Ilan University), Tomasz Kociumaka (Bar-Ilan University), Tsvi Kopelowitz (Bar-Ilan University), Ely Porat (Bar Ilan University)
Implementing geometric complexity theory: On the separation of orbit closures via symmetries (video)
Christian Ikenmeyer (University of Liverpool), Umangathan Kandasamy (Saarland University)
A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix (video)
Daniel Dadush (Centrum Wiskunde & Informatica, Amsterdam), Sophie Huiberts (Centrum Wiskunde & Informatica, Amsterdam), Bento Natura (London School of Economics and Political Science), László A. Végh (London School of Economics and Political Science)
21:10
Does Preprocessing help in Fast Sequence Comparisons? (video)
Elazar Goldenberg (The Academic College of Tel Aviv-Yaffo), Aviad Rubinstein (Stanford University), Barna Saha (University of California Berkeley)
The program-size complexity of self-assembled paths (video)
Pierre-Étienne Meunier (Hamilton Institute, Maynooth University), Damien Regnault (IBISC, Université Évry, Université Paris-Saclay), Damien Woods (Hamilton Institute, Maynooth University)
Solving Tall Dense Linear Programs in Nearly Linear Time (video)
Jan van den Brand (KTH Royal Institute of Technology), Yin Tat Lee (Microsoft Research), Aaron Sidford (Stanford University), Zhao Song (IAS / Princeton)
21:20
Dynamic Algorithms for LIS and Distance to Monotonicity (video)
Michael Mitzenmacher (Harvard University), Saeed Seddighin (Harvard University)
Efficient sampling and counting algorithms for the Potts model on $\mathbb Z^d$ at all temperatures (video)
Christian Borgs (Microsoft Research), Jennifer Chayes (Microsoft Research), Tyler Helmuth (University of Bristol), Will Perkins (University of Illinois at Chicago), Prasad Tetali (Georgia Institute of Technology)
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent (video)
Arun Jambulapati (Stanford University), Yin Tat Lee (University Washington), Jerry Li (Microsoft Research), Swati Padmanabhan (University of Washington), Kevin Tian (Stanford University)
21:30
Constant-factor approximation of near-linear edit distance in near-linear time (video)
Joshua Brakensiek (Stanford University), Aviad Rubinstein (Stanford University)

Constant factor approximations to edit distance on far input pairs in nearly linear time (video)
Michal Koucky (Charles University, Prague), Michael Saks (Rutgers Unviersity)
Catalytic Approaches to the Tree Evaluation Problem (video)
Ian Mertz (University of Toronto), James Cook (None)
Faster Energy Maximization for Faster Maximum Flow (video)
Yang P. Liu (Stanford University), Aaron Sidford (Stanford University)
  Thursday, June 25
 
Session 7A (stream)
Chair: Dana Ron
Session 7B (stream)
Chair: Henry Yuen
Session 7C (stream)
Chair: Ankit Garg
15:00
Breaching the 2-Approximation Barrier for Connectivity Augmentation: a Reduction to Steiner Tree (video)
Jaroslaw Byrka (University of Wroclaw), Fabrizio Grandoni (IDSIA, Switzerland), Afrouz Jabal Ameli (IDSIA, Switzerland)
Entanglement subvolume law for 2D frustration-free spin systems (video)
Anurag Anshu (University of Waterloo), Itai Arad (Technion), David Gosset (University of Waterloo)
On the Computability of Continuous Maximum Entropy Distributions with Applications (video)
Jonathan Leake (KTH), Nisheeth K. Vishnoi (Yale University)
15:10
A Spectral Approach to Network Design (video)
Lap Chi Lau (University of Waterloo), Hong Zhou (University of Waterloo)
Interactive shallow Clifford circuits: quantum advantage against NC$^1$ and beyond (video)
Daniel Grier (University of Waterloo), Luke Schaeffer (University of Waterloo)
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications (video)
Haotian Jiang (University of Washington), Yin Tat Lee (University of Washington, Microsoft Research Redmond), Zhao Song (IAS, Princeton University), Sam Wong (Microsoft Research Redmond)
15:20
Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4 (video)
Sidhanth Mohanty (University of California Berkeley), Prasad Raghavendra (University of California Berkeley), Jeff Xu (University of California Berkeley)
Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle) (video)
Matthew Coudron (IQC/University of Waterloo, University of Maryland/NIST), Sanketh Menda (University of Waterloo)

On the Need for Large Quantum Depth (video)
Nai-Hui Chia (University of Texas at Austin), Kai-Min Chung (Institute of Information Science, Academia Sinica), Ching-Yi Lai (Institute of Communications Engineering, National Chiao Tung University)
Does Learning Require Memorization? A Short Tale about a Long Tail (video)
Vitaly Feldman (Google Research)
15:30
Fast sampling and counting k-SAT solutions in the local lemma regime (video)
Weiming Feng (Nanjing University), Heng Guo (University of Edinburgh), Yitong Yin (Nanjing University), Chihao Zhang (Shanghai Jiao Tong University)
The Impossibility of Efficient Quantum Weak Coin Flipping (video)
Carl A. Miller (NIST, University of Maryland)
Efficiently Learning Structured Distributions from Untrusted Batches (video)
Sitan Chen (MIT), Jerry Li (Microsoft Research), Ankur Moitra (Math & CSAIL, MIT)
15:40 Break
16:00 Junior/Senior Lunch
17:00
Workshop 4: TCS Women Spotlight Workshop (stream)
Organizers: Sofya Raskhodnikova (Boston University), Barna Saha (UC Berkeley), Virginia Vassilevska Williams (MIT)
20:00 Break
 
Session 8A (stream)
Chair: Merav Parter
Session 8B (stream)
Chair: Robert Robere
Session 8C (stream)
Chair: Nika Haghtalab
21:00
All non-trivial variants of 3-LDT are equivalent (video)
Bartłomiej Dudek (University of Wrocław), Paweł Gawrychowski (University of Wrocław), Tatiana Starikovskaya (Ecole Normale Superieure)
No-Signaling Proofs with $O(\sqrt{\log n})$ Provers is in PSPACE (video)
Dhiraj Holden (MIT), Yael Tauman Kalai (Microsoft Research)
Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions (video)
Sepehr Assadi (Rutgers University), Hrishikesh Khandeparkar (Princeton University), Raghuvansh Saxena (Princeton University), S. Matthew Weinberg (Princeton University)
21:10
Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum (video)
Karl Bringmann (Max-Planck-Institute for Informatics), Vasileios Nakos (National Technical University of Athens)
Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions (video)
Shuichi Hirahara (National Institute of Informatics)
On the Nisan-Ronen conjecture for submodular valuations (video)
Giorgos Christodoulou (University of Liverpool), Elias Koutsoupias (University of Oxford), Annamaria Kovacs (Goethe University Frankfurt)
21:20
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut (video)
Amir Abboud (IBM Almaden Research Center), Vincent Cohen-Addad (CNRS, UPMC), Philip N Klein (Brown University)
Smoothed complexity of local Max-Cut and binary Max-CSP (video)
Emmanouil-Vasileios Vlatakis-Gkaragkounis (Columbia University), Xi Chen (Columbia University), Chenghao Guo (IIIS, Tsinghua University), Mihalis Yannakakis (Columbia University), Xinzhi Zhang (IIIS, Tsinghua University)
Towards a Better Understanding of Randomized Greedy Matching (video)
Zhihao Gavin Tang (Shanghai University of Finance and Economics), Xiaowei Wu (University of Vienna), Yuhao Zhang (The University of Hong Kong)
21:30
Constant Girth Approximation for Directed Graphs in Subquadratic Time (video)
Shiri Chechik (Tel-Aviv University), Yang P. Liu (Stanford University), Omer Rotem (Tel-Aviv University), Aaron Sidford (Stanford University)
How to lose at Monte Carlo: a simple dynamical system whose typical statistical behavior is non computable. (video)
Cristobal Rojas (Departamento de Matemáticas, Universidad Andres Bello, Chile.), Michael Yampolsky (Department of Mathematics, University of Toronto, Canada.)
Stochastic Matching with Few Queries: $(1-\varepsilon)$ Approximation (video)
Soheil Behnezhad (University of Maryland), Mahsa Derakhshan (University of Maryland), MohammadTaghi Hajiaghayi (University of Maryland)
  Friday, June 26
14:00 Social Event: Virtual Gather.town Meeting (all day long)
 
Session 9A (stream)
Chair: Christian Sohler
Session 9B (stream)
Chair: Ankit Garg
Session 9C (stream)
Chair: Piotr Indyk
15:00
Caching with Time Windows (video)
Anupam Gupta (Carnegie Mellon), Amit Kumar (IIT Delhi), Debmalya Panigrahi (Duke University)
Fooling Gaussian PTFs via Local Hyperconcentration (video)
Ryan O'Donnell (Carnegie Mellon University), Rocco A. Servedio (Columbia University), Li-Yang Tan (Stanford University)
Separations and Equivalences Between Turnstile Streaming and Linear Sketching (video)
John Kallaugher (The University of Texas at Austin), Eric Price (The University of Texas at Austin)
15:10
Online Vector Balancing and Geometric Discrepancy (video)
Nikhil Bansal (TU Eindhoven, and Centrum Wiskunde & Informatica), Haotian Jiang (Paul G. Allen School of CSE, University of Washington), Sahil Singla (Princeton University and Institute for Advanced Study), Makrand Sinha (CWI)
Extractors for Adversarial Sources via Extremal Hypergraphs (video)
Eshan Chattopadhyay (Cornell University), Jesse Goodman (Cornell University), Vipul Goyal (Carnegie Melon University), Xin Li (Johns Hopkins University)
Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits (video)
Sepehr Assadi (Rutgers University), Chen Wang (Rutgers University)
15:20
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue (video)
Zhiyi Huang (The University of Hong Kong), Qiankun Zhang (The University of Hong Kong)
Improved Analysis of Higher Order Random Walks and Applications (video)
Vedat Levi Alev (University of Waterloo), Lap Chi Lau (University of Waterloo)
Non-Adaptive Adaptive Sampling on Turnstile Streams (video)
Sepideh Mahabadi (TTIC), Ilya Razenshteyn (Microsoft Research), David P. Woodruff (Carnegie Mellon University), Samson Zhou (Carnegie Mellon University)
15:30
Unbounded lower bound for k-server against weak adversaries (video)
Marcin Bienkowski (University of Wroclaw), Jarosław Byrka (University of Wroclaw), Christian Coester (CWI), Łukasz Jez (University of Wroclaw)
Strong Self-Concordance and Sampling (video)
Aditi Laddha (Georgia Tech), Yin Tat Lee (University Washington), Santosh Vempala (Georgia Tech)
Fast Hashing with Strong Concentration Bounds (video)
Anders Aamand (University of Copenhagen), Jakob Bæk Tejs Knudsen (University of Copenhagen), Mathias Bæk Tejs Knudsen (SupWiz), Peter Michael Reichstein Rasmussen (University of Copenhagen), Mikkel Thorup (University of Copenhagen)
15:40 Break
17:00
Workshop 5: Algorithms with Predictions (stream)
Organizers: Piotr Indyk (MIT), Yaron Singer (Harvard), Ali Vakilian (University of Wisconsin-Madison), Sergei Vassilvitskii (Google)
Workshop 6: Derandomizing Space-Bounded Computation (stream)
Organizers: Raghu Meka (UCLA), Avishay Tal (UC Berkeley), David Zuckerman (UT Austin)
20:00 Break
 
Session 10A (stream)
Chair: Marek Cygan
Session 10B (stream)
Chair: Prahladh Harsha
Session 10C (stream)
Chair: Omri Weinstein
21:00
Three-in-a-tree in near linear time (video)
Kai-Yuan Lai (National Taiwan University), Hsueh-I Lu (National Taiwan University), Mikkel Thorup (University of Copenhagen)
Strong Average-Case Lower Bounds from Non-trivial Derandomization (video)
Lijie Chen (Massachusetts Institute of Technology), Hanlin Ren (Tsinghua University)
Distance Sensitivity Oracles With Subcubic Preprocessing Time and Fast Query Time (video)
Sarel Cohen (Tel-Aviv University), Shiri Chechik (Tel-Aviv University)
21:10
Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time (video)
Jesper Nederlof (Utrecht University)
Sharp Threshold Results for Computational Complexity (video)
Lijie Chen (MIT), Ce Jin (Tsinghua University), R. Ryan Williams (MIT)
Nearly Optimal Static Las Vegas Succinct Dictionary (video)
Huacheng Yu (Princeton University)
21:20
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths (video)
Daniel Lokshtanov (University of California Santa Barbara, USA), Pranabendu Misra (Max Planck Institute for Informatics, Saarbrucken, Germany), Michał Pilipczuk (University of Warsaw, Poland), Saket Saurabh (Institute of Mathematical Sciences, Chennai, India), Meirav Zehavi (Ben-Gurion University, Beersheba, Israel)
A Robust Version of Hegedus's Lemma, with Applications (video)
Srikanth Srinivasan (Department of Mathematics, IIT Bombay)
Lower Bound for Succinct Range Minimum Query (video)
Mingmou Liu (Nanjing University), Huacheng Yu (Princeton University)
21:30
Hitting Topological Minors is FPT (video)
Fedor V. Fomin (Department of Informatics, University of Bergen, Norway.), Daniel Lokshtanov (University of California Santa Barbara, USA), Fahad Panolan (Department of Computer Science and Engineering, IIT Hyderabad, India), Saket Saurabh (IMSc), Meirav Zehavi (Ben-Gurion University)
The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness (video)
Moran Feldman (University of Haifa), Ashkan Norouzi-Fard (Google Research), Ola Svensson (EPFL), Rico Zenklusen (ETH Zurich)
Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal (video)
Lingxiao Huang (Yale University), Nisheeth K. Vishnoi (Yale University)
21:40    
A Lower Bound for Parallel Submodular Minimization (video)
Eric Balkanski (Harvard University), Yaron Singer (Harvard University)
21:50 Social Event: Virtual Gather.town Meeting
23:00 TheoryFest and STOC 2020 conclude
The times listed in this table are in Universal Coordinated Time.