| The times listed below are in Eastern Standard Time. Poster sessions corresponding to each day’s paper sessions were held each evening from 12:00 midnight to 1:30 AM on Monday-Thursday, November 16-19. |
|||||||||||
| FOCS 2020 Program | |||||||||||
| Friday, November 13 | |||||||||||
| Tutorials Session | |||||||||||
| 11:00 – 12:30 |
What Can Theoretical Computer Science Contribute to the Discussion of Consciousness? Lenore Blum, Manuel Blum Video | Zoom Q&A session; call for feedback |
||||||||||
| 12:00 – 15:00 |
Computation in the Brain. Christos H. Papadimitriou, Santosh S. Vempala Slides 1 | Slides 2 | Slides 3 | Webpage | Video 1 | Video 2 |
||||||||||
| 13:00 – 16:00 |
Indistinguishability Obfuscation from Well-Founded Assumptions. Aayush Jain, Huijia Lin, Amit Sahai Videos: Part 1 | Part 2 | Part 3 | Live Presentation Video |
||||||||||
| 12:00 – 14:00 |
Theoretical Foundations of Reinforcement Learning. Alekh Agarwal, Akshay Krishnamurthy, John Langford Video | Webpage | Zoom Q&A session |
||||||||||
| 15:00 – 16:00 |
Cookbook: Lower Bounds for Statistical Inference in Distributed and Constrained Settings. Jayadev Acharya, Clément Canonne, Himanshu Tyagi Videos: Part 1 | Part 2| Part 3 | Part 4 | Zoom Q&A session; open problems |
||||||||||
| Not Live | Relaxed Locally Decodable Codes. Tom Gur, Igor Shinkar Videos: Part 1 | Part 2 | Part 3 | Part 4 | ||||||||||
| Not Live | Understanding Deep Learning: Challenges for Statistical Learning Theory. Peter Bartlett Video | ||||||||||
| Monday, November 16 | |||||||||||
| 10:30 | Welcome to FOCS 2020! Chaired by Sandy Irani | ||||||||||
| Session 1A – Complexity (Session Chair: Yuval Filmus) | Session 1B – Graph Algorithms (Session Chair: Talya Eden) | Session 1C – Learning (Session Chair: Andrej Risteski) | |||||||||
| 11:00 |
Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization Lijie Chen (MIT); Xin Lyu (Tsinghua); R. Ryan Williams (MIT) Paper | Long talk |
Near-linear Size Hypergraph Cut Sparsifiers Yu Chen (U. Penn.); Sanjeev Khanna (U. Penn.); Ansh Nagda (Univ. of Washington) Paper | Long talk |
Low-Degree Hardness of Random Optimization Problems David Gamarnik (MIT); Aukosh Jagannath (Waterloo); Alexander S. Wein (NYU Courant) Paper | Long talk |
||||||||
| 11:15 |
On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds Lijie Chen (MIT); Ron D. Rothblum (Technion, MIT, Weizmann); Roei Tell (Weizmann, MIT); Eylon Yogev (BU, Tel Aviv) Paper | Long talk |
Towards Better Approximation of Graph Crossing Number Julia Chuzhoy (TTI Chicago); Sepideh Mahabadi (TTI Chicago); Zihan Tan (Univ. of Chicago) Paper | Long talk |
List Decodable Mean Estimation in Nearly Linear Time Yeshwanth Cherapanamjeri (UC Berkeley); Sidhanth Mohanty (UC Berkeley); Morris Yau (UC Berkeley) Paper | Long talk |
||||||||
| 11:30 |
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity Susanna F. de Rezende (Czech Academy); Or Meir (Haifa); Jakob Nordstrom (Copenhagen, Lund); Toniann Pitassi (Toronto, IAS); Robert Robere (DIMACS, Toronto, IAS); Marc Vinyals (Technion) Paper | Long talk |
Deterministic Min-cut in Poly-logarithmic Max-flows Jason Li (CMU); Debmalya Panigrahi (Duke) Paper | Long talk |
Outlier-Robust clustering of Gaussians and other non-spherical mixtures Ainesh Bakshi (CMU); Ilias Diakonikolas (UW Madison); Sam Hopkins (Berkeley); Daniel Kane (UCSD); Sushrut Karmalkar (UT Austin); Pravesh K Kothari (CMU) Paper | Paper | Long talk |
||||||||
| 11:45 |
Tree-depth and the Formula Complexity of Subgraph Isomorphism Deepanshu Kush (Toronto); Benjamin Rossman (Duke) Paper | Long talk |
Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs Kyriakos Axiotis (MIT); Aleksander Madry (MIT); Adrian Vladu (BU) Paper | Long talk |
Collaborative Top Distribution Identifications with Limited Interaction Nikolai Karpov (IU Bloomington); Qin Zhang (IU Bloomington); Yuan Zhou (UIUC) Paper | Long talk |
||||||||
| 12:00 |
KRW Composition Theorems via Lifting Susanna F. de Rezende (Czech Academy); Or Meir (Haifa); Jakob Nordstrom (Copenhagen, Lund); Toniann Pitassi (Toronto); Robert Robere (DIMACS, Toronto, IAS) Paper | Long talk |
Cut-Equivalent Trees are Optimal for Min-Cut Queries Amir Abboud (IBM); Robert Krauthgamer (Weizmann); Ohad Trabelsi (Weizmann) Paper | Long talk |
Kernel Density Estimation through Density Constrained Near Neighbor Search Moses Charikar (Stanford); Michael Kapralov (EPFL); Navid Nouri (EPFL); Paris Siminelakis (UC Berkeley) Paper | Long talk |
||||||||
| 12:15 |
Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity Shuichi Hirahara (National Institute of Informatics) Paper | Long talk |
Unit Capacity Maxflow in Almost m^{4/3} time Tarun Kathuria (UC Berkeley); Yang P. Liu (Stanford); Aaron Sidford (Stanford) Paper | Paper | Long talk |
Small Covers for Near-zero Sets of Polynomials and Learning Latent Variable Models Ilias Diakonikolas (UW Madison); Daniel Kane (UCSD) Paper | Long talk |
||||||||
| Session 2A – Quantum I (Session Chair: John Wright) | Session 2B – Algorithmic Game Theory (AGT) (Session Chair: Nicole Immorlica) | Session 2C – Streaming and Distributed Algorithms (Session Chair: Dan Alistarh) | |||||||||
| 14:00 |
QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge Anne Broadbent (Ottawa); Alex Grilo (CWI and QuSoft) Paper | Long talk |
Mechanisms for a No-Regret Agent: Beyond the Common Prior Modibo K Camara (NWU); Jason Hartline (NWU); Aleck Johnsen (NWU) Paper | Long talk |
The Coin Problem with Applications to Data Streams Mark Barverman (Princeton); Sumegha Garg (Princeton); David Woodruff (CMU) Paper | Long talk |
||||||||
| 14:15 |
Tight Limits on Nonlocality from Nontrivial Communication Complexity; aka Reliable Computation with Asymmetric Gate Noise Noah Shutty (Stanford); Mary Wootters (Stanford); Patrick Hayden (Stanford) Paper | Long talk |
Smoothed Complexity of 2-player Nash Equilibria Shant Boodaghians (UIUC); Joshua Brakensiek (Stanford); Samuel B. Hopkins (UC Berkeley); Aviad Rubinstein (Stanford) Paper | Long talk |
Optimal Streaming Approximations for all Boolean Max 2-CSPs and Max k-SAT Chi-Ning Chou (Harvard); Alexander Golovnev (Harvard); Santhoshini Velusamy (Harvard) Paper | Long talk |
||||||||
| 14:30 |
Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders Shai Evra (IAS); Tali Kaufman (Bar Ilan); Gilles Zemor (Bordeaux) Paper | Long talk |
Communication complexity of Nash equilibrium in potential games Yakov Babichenko (Technion, IIT); Aviad Rubinstein (Stanford) Paper | Long talk |
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms Sepehr Assadi (Rutgers); Ran Raz (Princeton) Paper | Long talk |
||||||||
| 14:45 |
Towards Optimal Separations between Quantum and Randomized Query Complexities Avishay Tal (UC Berkeley) Paper | Long talk |
Coordinate Methods for Matrix Games Yair Carmon (Stanford); Yujia Jin (Stanford); Aaron Sidford (Stanford); Kevin Tian (Stanford) Paper | Long talk |
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems Sepehr Assadi (Rutgers); Gillat Kol (Princeton); Raghuvansh Saxena (Princeton); Huacheng Yu (Princeton) Paper | Long talk |
||||||||
| 15:00 |
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions Shalev Ben-David (Waterloo); Eric Blais (Waterloo) Paper | Long talk |
Benchmark Design and Prior-independent Optimization Jason Hartline (NWU); Aleck Johnsen (NWU); Yingkai Li (NWU) Paper | Long talk |
Distributed Lower Bounds for Ruling Sets Alkida Balliu (Univ. of Freiburg); Sebastian Brandt (ETH Zurich); Dennis Olivetti (Univ. of Freiburg) Paper | Long talk |
||||||||
| 15:15 |
Towards a Proof of the Fourier Entropy Conjecture? Esty Kelman (Tel Aviv); Guy Kindler (Hebrew Univ); Noam Lifshitz (Hebrew Univ); Dor Minzer (IAS); Muli Safra (Tel Aviv) Paper | Long talk |
An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions Paul Duetting (Google Research, LSE); Thomas Kesselheim (Univ. of Bonn); Brendan Lucier (Microsoft Research) Paper | Long talk |
Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization Yi-Jun Chang (ETH Zurich); Thatchaphol Saranurak (TTI Chicago) Paper | Long talk |
||||||||
| 16:00 | Knuth Prize Lecture: Cynthia Dwork | ||||||||||
| Poster Sessions | |||||||||||
| 24:00 | Session 1A | Session 1B | Session 1C | Session 2A | Session 2B | Session 2C | |||||
| Tuesday, November 17 | |||||||||||
| Session 3A: Plenary Session (Session Chair: Sandy Irani) | |||||||||||
| 11:00 – 12:30 |
An Equivalence Between Private Classification and Online Prediction. Mark Bun (BU); Roi Livni (Tel-Aviv Univ.); Shay Moran (Google AI) Paper | Long talk |
||||||||||
|
A New Minimax Theorem for Randomized Algorithms. Shalev Ben-David (Waterloo); Eric Blais (Waterloo) Paper | Long talk |
|||||||||||
|
Edge-Weighted Online Bipartite Matching. Matthew Fahrbach (Google Research); Zhiyi Huang (HKU); Runzhou Tao (Columbia ); Morteza Zadimoghaddam (Google Research) Paper | Long talk |
|||||||||||
|
The Constant Depth Formula and Partial Function Versions of MCSP are Hard. Rahul Ilango (MIT) Paper | Long talk |
|||||||||||
| 12:45 – 13:45 | Junior Senior Lunch | ||||||||||
| Session 4A – Coding Theory (Session Chair: Yuval Filmus) | Session 4B – Matrix Methods (Session Chair: Andrej Risteski) | Session 4C – Graph Algorithms and Coding Session Chair: Shay Mozes) | |||||||||
| 14:00 |
Unique Decoding of Explicit $\epsilon$-balanced Codes Near the Gilbert–Varshamov Bound Fernando Granha Jeronimo (Chicago); Dylan Quintana (Chicago); Shashank Srivastava (TTI Chicago); Madhur Tulsiani (TTI Chicago) Paper | Long talk |
Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation Ainesh Bakshi (CMU); Nadiia Chepurko (MIT); David Woodruff (CMU) Paper | Long talk |
Adjacency Labelling for Planar Graphs (and Beyond) Vida Dujmovic (Ottawa); Louis Esperet (CNRS, Universiti Grenoble Alpes); Cyril Gavoille (Bordeaux); Gwenakl Joret (Universiti Libre de Bruxelles); Piotr Micek (Jagiellonian); Pat Morin (Carleton University) Paper | Long talk |
||||||||
| 14:15 |
Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes Zvika Brakerski (Weizmann); Yael Tauman Kalai (Microsoft, MIT); Raghuvansh Saxena (Princeton) Paper | Long talk |
Near Optimal Linear Algebra in the Online and Sliding Window Models Vladimir Braverman (JHU); Petros Drineas ( Purdue); Cameron Musco (U Mass Amherst); Christopher Musco (NYU); Jalaj Upadhyay (Apple); David Woodruff (CMU); Samson Zhou (CMU) Paper | Long talk |
On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs Vincent Cohen-Addad (Google Research); Arnold Filtser (Columbia); Philip N. Klein (Brown); Hung Le (Univ. of Victoria, U Mass Amherst) Paper | Long talk |
||||||||
| 14:30 |
LDPC Codes Achieve List Decoding Capacity Jonathan Mosheiff (CMU); Nicolas Resch (CMU); Noga Ron-Zewi (Haifa); Shashwat Silas (Stanford); Mary Wootters (Stanford) Paper | Long talk |
Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time Jess Banks (UC Berkeley); Jorge Garza Vargas (UC Berkeley); Archit Kulkarni (UC Berkeley); Nikhil Srivastava (UC Berkeley) Paper | Long talk |
Twin-width I: tractable FO model checking Edouard Bonnet (LIP, ENS Lyon); Eun Jung Kim (LAMSADE, Dauphine); Stiphan Thomassi (LIP, ENS Lyon); Rimi Watrigant (LIP, ENS Lyon) Paper | Long talk |
||||||||
| 14:45 |
Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$) Klim Efremenko (Ben-Gurion); Gillat Kol (Princeton); Raghuvansh Saxena (Princeton) Paper | Long talk |
Algorithms and Hardness for Linear Algebra on Geometric Graphs Josh Alman (Harvard ); Timothy Chu (CMU); Aaron Schild (UW); Zhao Song (Princeton/IAS) Paper | Long talk |
Independent Set on P_k-Free Graphs in Quasi-Polynomial Time Peter Gartland (UC); Daniel Lokshtanov (UC) Paper | Long talk |
||||||||
| 15:00 |
Coded trace reconstruction in a constant number of traces Joshua Brakensiek (Stanford ); Ray Li (Stanford ); Bruce Spang (Stanford ) |
Sparse PCA: algorithms, adversarial perturbations and certificates Tommaso d’Orsi (ETH Zurich); Pravesh K. Kothari (CMU); Gleb Novikov (ETH Zurich); David Steurer (ETH Zurich) Paper | Long talk |
Isomorphism Testing for Graphs Excluding Small Minors Martin Grohe (RWTH Aachen Univ.); Daniel Neuen (CISPA Helmholtz Center); Daniel Wiebking (RWTH Aachen Univ.) Paper | Long talk |
||||||||
| 15:15 |
Network Coding Gaps for Completion Times of Multiple Unicasts Bernhard Haeupler (CMU); David Wajc (CMU); Goran Zuzic (CMU) Paper | Long talk |
Maximizing Determinants under Matroid Constraints Vivek Madan (Amazon); Aleksandar Nikolov (Univ. of Toronto); Mohit Singh (Georgia Tech); Uthaipon Tantipongpipat (Twitter) Paper | Long talk |
|||||||||
| 16:00 | Reports Session and Award Presentations | ||||||||||
| Poster Sessions | |||||||||||
| 24:00 | Session 3 | Session 4A | Session 4B | Session 4C | |||||||
| Wednesday, November 18 | |||||||||||
| Session 5A – Quantum II (Session Chair: Robin Kothari) | Session 5B – Scheduling and Data Structures (Session Chair: Michal Koucky) | Session 5C – Graph Algorithms and Coding (Session Chair: Sungjin Im) | |||||||||
| 11:00 |
Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving. Simon Apers (ULB, CWI); Ronald de Wolf (QuSoft, CWI, Univ. of Amsterdam) Paper | Long talk |
Lazy Search Trees. Bryce Sandlund (Waterloo); Sebastian Wild (Liverpool) Paper | Long talk |
New Techniques for Proving Fine-Grained Average-Case Hardness. Mina Dalirrooyfard (MIT); Andrea Lincoln (MIT); Virginia Vassilevska Williams (MIT) Paper | Long talk |
||||||||
| 11:15 |
Symmetries, graph properties, and quantum speedups. Shalev Ben-David (Waterloo); Andrew Childs (UMD); Andras Gilyin (Caltech); William Kretschmer (UT); Supartha Podder (Ottawa); Daochen Wang (UMD) Paper | Long talk |
2D Fractional Cascading on Axis-aligned Planar Subdivisions. Peyman Afshani (Aarhus); Pingan Cheng (Aarhus) Paper | Long talk |
Monochromatic Triangles, Triangle Listing and APSP. Virginia Williams (MIT); Yinzhan Xu (MIT) Paper | Long talk |
||||||||
| 11:30 |
Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. Laura Mančinska (Copenhagen); David E. Roberson (Technical Univ., Denmark) Paper | Long talk |
Subsets and Supermajorities: Optimal Hashing-based Set Similarity Search. Thomas Ahle (BARC, IT Univ. Copenhagen); Jakob Knudsen (BARC, Univ. Copenhagen) Paper | Long talk |
A Parameterized Approximation Scheme for Min k-Cut Daniel Lokshtanov (UC); Saket Saurabh (IMS, HBNI); Vaishali Surianarayanan (UC) Paper | Long talk |
||||||||
| 11:45 |
Tight Quantum Time-Space Tradeoffs for Function Inversion. Kai-Min Chung (Academia Sinica); Siyao Guo (NYU Shanghai); Qipeng Liu (Princeton, NTT Research); Luowen Qian (BU) Paper | Long talk |
Polynomial Data Structure Lower Bounds in the Group Model. Alexander Golovnev (Harvard); Gleb Posobin (Columbia); Oded Regev (NYU); Omri Weinstein (Columbia) Paper | Long talk |
Hypergraph k-cut for fixed k in deterministic polynomial time. Karthekeyan Chandrasekaran (UIUC); Chandra Chekuri (UIUC) Paper | Long talk |
||||||||
| 12:00 |
Sample-efficient learning of quantum many-body systems. Anurag Anshu (IQC, Waterloo); Srinivasan Arunachalam (IBM Research); Tomotaka Kuwahara (RIKEN Center for AI); Mehdi Soleimanifar (MIT) Paper | Long talk |
An Adaptive Step Toward the Multiphase Conjecture and Lower Bounds on Nonlinear Networks. Young Kun Ko (NYU); Omri Weinstein (Columbia) Paper | Long talk |
Scheduling with Communication Delays via LP Hierarchies and Clustering. Sami Davies (UW); Janardhan Kulkarni (Microsoft Research); Thomas Rothvoss (UW); Jakub Tarnawski (Microsoft Research); Yihao Zhang (UW) Paper | Long talk |
||||||||
| 12:15 |
Entanglement Is Necessary for Optimal Quantum Property Testing. Sebastien Bubeck (MSR); Sitan Chen (MIT); Jerry Li (MSR) Paper | Long talk |
Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations. Ariel Kulik (Technion); Hadas Shachnai (Technion) Paper | Long talk |
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay. Biswaroop Maiti (Northeastern); Rajmohan Rajaraman (Northeastern); David Stalfa (Northeastern); Zoya Svitkina (Google); Aravindan Vijayaraghavan (NWU) Paper | Long talk |
||||||||
| 12:45 – 13:45 | Junior Senior Lunch | ||||||||||
| Session 6A – Complexity and Coding Theory (Session Chair: Elena Grigorescu) | Session 6B – Matrix Methods (Session Chair: Alexandra Kolla) | Session 6C – Strings and Geometry (Session Chair: Shay Mozes) | |||||||||
| 14:00 |
Local Proofs Approaching the Witness Length. Noga Ron-Zewi (Haifa); Ron Rothblum (Technion) Paper | Long talk |
A Faster Interior Point Method for Semidefinite Programming. Haotian Jiang (UW); Tarun Kathuria (UC Berkeley); Yin Tat Lee (UW); Swati Padmanabhan (UW); Zhao Song (Princeton, IAS) Paper | Long talk |
Faster Approximate Pattern Matching: A Unified Approach. Panagiotis Charalampopoulos (Kings College London); Tomasz Kociumaka (Bar-Ilan Univ., Univ. of Warsaw); Philip Wellnitz (MPII, SIC) Paper | Long talk |
||||||||
| 14:15 |
Rigid Matrices from Rectangular PCPs. Amey Bhangale (UC Riverside); Prahladh Harsha (TIFR); Orr Paradise (UC Berkeley); Avishay Tal (UC Berkeley) Paper | Long talk |
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. Jan van den Brand (KTH); Yin Tat Lee (UW, Microsoft Research); Danupon Nanongkai (KTH); Richard Peng (Georgia Tech); Thatchaphol Saranurak (TTI Chicago); Aaron Sidford (Stanford); Zhao Song (Princeton, IAS); Di Wang (Google Research) Paper | Long talk |
Edit Distance in Near-Linear Time: it’s a Constant Factor. Alexandr Andoni (Columbia); Negev Shekel Nosatzki (Columbia) Paper | Long talk |
||||||||
| 14:30 |
On the Existence of Algebraically Natural Proofs. Prerona Chatterjee (TIFR); Mrinal Kumar (IIT Bombay); C. Ramya (TIFR); Ramprasad Saptharishi (TIFR); Anamay Tengse (TIFR) Paper | Long talk |
Revisiting Tardos’s Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers. Daniel Dadush (CWI); Bento Natura (LSE); Laszlo Vegh (LSE) Paper | Long talk |
Resolution of the Burrows-Wheeler Transform Conjecture. Dominik Kempa (UC Berkeley); Tomasz Kociumaka (Bar-Ilan Univ.) Paper | Long talk |
||||||||
| 14:45 |
Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties. Visu Makam (IAS); Avi Wigderson (IAS) Paper | Long talk |
Subexponential LPs Approximate Max-Cut. Samuel Hopkins (UC Berkeley); Tselil Schramm (Stanford); Luca Trevisan (Bocconi Univ.) Paper | Long talk |
Framework for $\exists\mathbb R$-Completeness of Two-Dimensional Packing Problems. Mikkel Abrahamsen (Univ. of Copenhagen); Tillmann Miltzow (Utrecht Univ.); Nadja Seiferth (Freie Universitdt Berlin) Paper | Long talk |
||||||||
| 15:00 |
Learning sums of powers of low-degree polynomials in the non-degenerate case. Ankit Garg (MS Research); Neeraj Kayal (MS Research); Chandan Saha (Indian Institute of Science) Paper | Long talk |
Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes. Mrinalkanti Ghosh (TTIC); Fernando Granha Jeronimo (Chicago); Chris Jones (Chicago); Aaron Potechin (Chicago); Goutham Rajendran (Chicago) Paper | Long talk |
Smoothing the gap between NP and ER. Jeff Erickson (UIUC); Ivor van der Hoog (Utrecht Univ.); Tillmann Miltzow (Utrecht Univ.) Paper | Long talk |
||||||||
| 15:15 |
Proximity gaps for Reed-Solomon Codes. Eli Ben-Sasson (StarkWare); Dan Carmon (StarkWare); Yuval Ishai (Technion); Swastik Kopparty (Rutgers); Shubhangi Saraf (Rutgers) Paper | Long talk |
Approximation Algorithms for Stochastic Minimum Norm Combinatorial Optimization. Sharat Ibrahimpur (Waterloo); Chaitanya Swamy (Waterloo) Paper | Long talk |
Point Location and Active Learning: Learning Halfspaces Almost Optimally. Max Hopkins (UCSD); Daniel Kane (UCSD); Shachar Lovett (UCSD); Gaurav Mahajan (UCSD) Paper | Long talk |
||||||||
| 16:00 | Business Meeting | ||||||||||
| Poster Sessions | |||||||||||
| 24:00 | Session 5A | Session 5B | Session 5C | Session 6A | Session 6B | Session 6C | |||||
| Thursday, November 19 | |||||||||||
| Session 7A – Graph Algorithms + Graph Theory (Session Chair: Alexandra Kolla) | Session 7B – Dynamic Graphs (Session Chair: Jugal Garg) | Session 7C – Streaming and Learning Algorithms (Session Chair: Paul Valiant) | |||||||||
| 11:00 |
Explicit near-fully X-Ramanujan graphs. Ryan O’Donnell (CMU); Xinyu Wu (CMU) Paper | Long talk |
Near-Optimal Decremental SSSP in Dense Weighted Digraphs. Aaron Bernstein (Rutgers); Maximilian Gutenberg (Univ. of Copenhagen); Christian Wulff-Nilsen (Univ. of Copenhagen) Paper | Long talk |
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance. Tomasz Kociumaka (Bar-Ilan Univ.); Barna Saha (UC Berkeley) Paper | Long talk |
||||||||
| 11:15 |
Nearly Optimal Pseudorandomness From Hardness. Dean Doron (Stanford); Dana Moshkovitz (UT); Justin Oh (UT); David Zuckerman (UT) Paper | Long talk |
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing. Aaron Bernstein (Rutgers); Maximilian Gutenberg (Univ. of Copenhagen); Thatchaphol Saranurak (TTIC) Paper | Long talk |
Testing linear-invariant properties. Jonathan Tidor (MIT); Yufei Zhao (MIT) Paper | Long talk |
||||||||
| 11:30 |
Correlated Pseudorandom Functions from Variable-Density LPN. Elette Boyle (IDC Herzliya); Geoffroy Couteau (IRIF); Niv Gilboa (Ben-Gurion Univ.); Yuval Ishai (Technion); Lisa Kohl (Technion); Peter Scholl (Aarhus Univ.) Paper | Long talk |
Fast Dynamic Cuts, Distances and Effective Resistance via Vertex Sparsifier. Li Chen (Georgia Tech); Gramoz Goranci (Univ. of Toronto); Monika Henzinger (Univ. of Vienna); Richard Peng (Georgia Tech); Thatchaphol Saranurak (TTI Chicago) Paper | Long talk |
Testing Positive Semi-Definiteness via Random Submatrices. Ainesh Bakshi (CMU); Nadiia Chepurko (MIT); Rajesh Jayaram (CMU) Paper | Long talk |
||||||||
| 11:45 |
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature. Andrew Drucker (Univ. of Chicago) |
Fully-Dynamic Submodular Cover with Bounded Recourse. Anupam Gupta (CMU); Roie Levin (CMU) Paper | Long talk |
Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time. Mahdi Cheraghchi (UMich); Vasileios Nakos (Saarland Univ.) Paper | Long talk |
||||||||
| 12:00 |
A Dichotomy for Real Boolean Holant Problems. Shuai Shao (UW-Madison); Jin-Yi Cai (UW-Madison) Paper | Long talk |
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. Julia Chuzhoy (TTI Chicago); Yu Gao (Georgia Tech); Jason Li (CMU); Danupon Nanongkai (KTH); Richard Peng (Georgia Tech); Thatchaphol Saranurak (TTI Chicago) Paper | Long talk |
Pandoras Box with Correlations: Learning and Approximation. Shuchi Chawla (UW Madison); Evangelia Gergatsouli (UW Madison); Yifeng Teng (UW Madison); Christos Tzamos (UW Madison); Ruimin Zhang (UW Madison) Paper | Long talk |
||||||||
| 12:15 |
Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs. Jin-Yi Cai (UW-Madison); Artsiom Hovarau (UW-Madison) Paper | Long talk |
||||||||||
| Session 8A – Crypto (Session Chair: Tal Malkin) | Session 8B – Dynamic Graphs (Session Chair: Nike Sun) | Session 8C – Algorithmic Game Theory (Session Chair: Nikhil Devanur) | |||||||||
| 14:00 |
Extractors and Secret Sharing Against Bounded Collusion Protocols. Eshan Chattopadhyay (Cornell); Jesse Goodman (Cornell); Vipul Goyal (CMU); Ashutosh Kumar (UCLA); Xin Li (JHU); Raghu Meka (UCLA); David Zuckerman (UT) Paper | Paper | Long talk |
High-precision Estimation of Random Walks in Small Space. AmirMahdi Ahmadinejad (Stanford); Jonathan Kelner (MIT); Jack Murtagh (Harvard); John Peebles (Yale); Aaron Sidford (Stanford); Salil Vadhan (Harvard) Paper | Long talk |
Beyond Tree Embeddings – a Deterministic Framework for Network Design with Deadlines or Delay. Yossi Azar (Tel Aviv Univ.); Noam Touitou (Tel Aviv Univ.) Paper | Long talk |
||||||||
| 14:15 |
On One-way Functions and Kolmogorov Complexity. Yanyi Liu (Cornell); Rafael Pass (Cornell Tech) Paper | Long talk |
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. Zongchen Chen (Georgia Tech); Kuikui Liu (UW); Eric Vigoda (Georgia Tech) Paper | Long talk |
Fully Online Matching II: Beating Ranking and Water-filling. Zhiyi Huang (HKU); Zhihao Gavin Tang (ITCS, SUFE); Xiaowei Wu (IOTSC, Univ. of Macau); Yuhao Zhang (HKU) Paper | Long talk |
||||||||
| 14:30 |
Is it Easier to Prove Statements that are Guaranteed to be True? Rafael Pass (Cornell Tech); Muthuramakrishnan Venkitasubramaniam (U. Rochester) Paper | Long talk |
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. Nima Anari (Stanford); Kuikui Liu (UW); Shayan Oveis Gharan (UW) Paper | Long talk |
Stochastic Weighted Matching: $(1-\epsilon)$ Approximation. Soheil Behnezhad (UMD); Mahsa Derakhshan (UMD) Paper | Long talk |
||||||||
| 14:45 |
A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip. Iftach Haitner (Tel Aviv Univ.); Yonatan Karidi-Heller (Tel Aviv Univ.) Paper | Long talk |
Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases. Nima Anari (Stanford); Michal Derezinski (UC-Berkeley) Paper | Long talk |
Optimal anytime regret with two experts. Nicholas Harvey (UBC); Christopher Liaw (UBC); Edwin Perkins (UBC); Sikander Randhawa (UBC) Paper | Long talk |
||||||||
| 15:00 |
The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency. Benny Applebaum (Tel Aviv Univ.); Eliran Kachlon (Tel Aviv Univ.); Arpita Patra (IIS, Bangalore) Paper | Long talk |
The complexity of approximating averages on bounded-degree graphs.
Andreas Galanis (Oxford); Daniel Stefankovic (Univ. of Rochester); Eric Vigoda (Georgia Tech) |
AdWords in a Panorama. Zhiyi Huang (HKU); Qiankun Zhang (HKU); Yuhao Zhang (HKU) Paper | Long talk |
||||||||
| 15:15 |
A constant rate non-malleable code in the split-state model. Divesh Aggarwal (National Univ. of Singapore); Maciej Obremski (National Univ. of Singapore) Paper | Long talk |
Counting Small Induced Subgraphs Satisfying Monotone Properties. Marc Roth (Merton, Oxford); Johannes Schmitt (Math Institute, Univ. of Bonn); Philip Wellnitz (MPII, SIC, Germany) Paper | Long talk |
Resolving the Optimal Metric Distortion Conjecture. Vasilis Gkatzelis (Drexel); Daniel Halpern (Univ. of Toronto); Nisarg Shah (Univ. of Toronto) Paper | Long talk |
||||||||
| Poster Sessions | |||||||||||
| 24:00 | Session7A | Session 7B | Session 7C | Session 8A | Session 8B | Session 8C | |||||
| FOCS 2020: Conclusion | |||||||||||