The times listed below are in Eastern Standard Time.
Poster sessions corresponding to each day’s paper sessions are held each evening from 12:00 midnight to 1:30 AM.
FOCS 2020 Program
Monday, November 16
10:30 Welcome to FOCS 2020!  Chaired by Sandy Irani
Session 1A Session 1B Session 1C
11:00 Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization
Lijie Chen (MIT); Xin Lyu (Tsinghua); R. Ryan Williams (MIT)
Paper | Long talk | Session | Poster
Near-linear Size Hypergraph Cut Sparsifiers
Yu Chen (U. Penn.); Sanjeev Khanna (U. Penn.); Ansh Nagda (Univ. of Washington)
Paper | Long talk | Session | Poster
Low-Degree Hardness of Random Optimization Problems
David Gamarnik (MIT); Aukosh Jagannath (Waterloo); Alexander S. Wein (NYU Courant)
Paper | Long talk | Session | Poster
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 | Session | Poster
Towards Better Approximation of Graph Crossing Number
Julia Chuzhoy (TTI Chicago); Sepideh Mahabadi (TTI Chicago); Zihan Tan (Univ. of Chicago)
Paper | Long talk | Session | Poster
List Decodable Mean Estimation in Nearly Linear Time
Yeshwanth Cherapanamjeri (UC Berkeley); Sidhanth Mohanty (UC Berkeley); Morris Yau (UC Berkeley)
Paper | Long talk | Session | Poster
11:30 Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Susanna F. de Rezende (Czech Academy); Or Meir (Haifa); Jakob Nordstrvm (Copenhagen, Lund); Toniann Pitassi (Toronto, IAS); Robert Robere (DIMACS, Toronto, IAS); Marc Vinyals (Technion)
Paper | Long talk | Session | Poster
Deterministic Min-cut in Poly-logarithmic Max-flows
Jason Li (CMU); Debmalya Panigrahi (Duke)
Paper | Long talk | Session | Poster
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 | Session | Poster
11:45 Tree-depth and the Formula Complexity of Subgraph Isomorphism
Deepanshu Kush (Toronto); Benjamin Rossman (Duke)
Paper | Long talk | Session | Poster
Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs
Kyriakos Axiotis (MIT); Aleksander Madry (MIT); Adrian Vladu (BU)
Paper | Long talk | Session | Poster
Collaborative Top Distribution Identifications with Limited Interaction
Nikolai Karpov (IU Bloomington); Qin Zhang (IU Bloomington); Yuan Zhou (UIUC)
Paper | Long talk | Session | Poster
12:00 KRW Composition Theorems via Lifting
Susanna F. de Rezende (Czech Academy); Or Meir (Haifa); Jakob Nordstrvm (Copenhagen, Lund); Toniann Pitassi (Toronto); Robert Robere (DIMACS, Toronto, IAS)
Paper | Long talk | Session | Poster
Cut-Equivalent Trees are Optimal for Min-Cut Queries
Amir Abboud (IBM); Robert Krauthgamer (Weizmann); Ohad Trabelsi (Weizmann)
Paper | Long talk | Session | Poster
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 | Session | Poster
12:15 Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity
Shuichi Hirahara (National Institute of Informatics)
Paper | Long talk | Session | Poster
Unit Capacity Maxflow in Almost m^{4/3} time
Tarun Kathuria (UC Berkeley); Yang P. Liu (Stanford); Aaron Sidford (Stanford)
Paper | Paper | Long talk | Session | Poster
Small Covers for Near-zero Sets of Polynomials and Learning Latent Variable Models
Ilias Diakonikolas (UW Madison); Daniel Kane (UCSD)
Paper | Long talk | Session | Poster
Session 2A Session 2B Session 2C
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 | Session | Poster
Mechanisms for a No-Regret Agent: Beyond the Common Prior
Modibo K Camara (NWU); Jason Hartline (NWU); Aleck Johnsen (NWU)
Paper | Long talk | Session | Poster
The Coin Problem with Applications to Data Streams
Mark Barverman (Princeton); Sumegha Garg (Princeton); David Woodruff (CMU)
Paper | Long talk | Session | Poster
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 | Session | Poster
Smoothed Complexity of 2-player Nash Equilibria
Shant Boodaghians (UIUC); Joshua Brakensiek (Stanford); Samuel B. Hopkins (UC Berkeley); Aviad Rubinstein (Stanford)
Paper | Long talk | Session | Poster
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 | Session | Poster
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 | Session | Poster
Communication complexity of Nash equilibrium in potential games
Yakov Babichenko (Technion, IIT); Aviad Rubinstein (Stanford)
Paper | Long talk | Session | Poster
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
Sepehr Assadi (Rutgers); Ran Raz (Princeton)
Paper | Long talk | Session | Poster
14:45 Towards Optimal Separations between Quantum and Randomized Query Complexities
Avishay Tal (UC Berkeley)
Paper | Long talk | Session | Poster
Coordinate Methods for Matrix Games
Yair Carmon (Stanford); Yujia Jin (Stanford); Aaron Sidford (Stanford); Kevin Tian (Stanford)
Paper | Long talk | Session | Poster
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 | Session | Poster
15:00 A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions
Shalev Ben-David (Waterloo); Eric Blais (Waterloo)
Paper | Long talk | Session | Poster
Benchmark Design and Prior-independent Optimization
Jason Hartline (NWU); Aleck Johnsen (NWU); Yingkai Li (NWU)
Paper | Long talk | Session | Poster
Distributed Lower Bounds for Ruling Sets
Alkida Balliu (Univ. of Freiburg); Sebastian Brandt (ETH Zurich); Dennis Olivetti (Univ. of Freiburg)
Paper | Long talk | Session | Poster
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 | Session | Poster
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 | Session | Poster
Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
Yi-Jun Chang (ETH Zurich); Thatchaphol Saranurak (TTI Chicago)
Paper | Long talk | Session | Poster
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 3: Plenary Session
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 | Session | Poster
A New Minimax Theorem for Randomized Algorithms.
Shalev Ben-David (Waterloo); Eric Blais (Waterloo)
Paper | Long talk | Session | Poster
Edge-Weighted Online Bipartite Matching.
Matthew Fahrbach (Google Research); Zhiyi Huang (HKU); Runzhou Tao (Columbia ); Morteza Zadimoghaddam (Google Research)
Paper | Long talk | Session | Poster
The Constant Depth Formula and Partial Function Versions of MCSP are Hard.
Rahul Ilango (MIT)
Paper | Long talk | Session | Poster
Session 4A Session 4B Session 4C
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 | Session | Poster
Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation
Ainesh Bakshi (CMU); Nadiia Chepurko (MIT); David Woodruff (CMU)
Paper | Long talk | Session | Poster
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 | Session | Poster
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 | Session | Poster
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 | Session | Poster
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 | Session | Poster
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 | Session | Poster
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 | Session | Poster
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 | Session | Poster
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 | Session | Poster
Algorithms and Hardness for Linear Algebra on Geometric Graphs
Josh Alman (Harvard ); Timothy Chu (CMU); Aaron Schild (UW); Zhao Song (magic.linuxkde@gmail.com)
Paper | Long talk | Session | Poster
Independent Set on P_k-Free Graphs in Quasi-Polynomial Time
Peter Gartland (UC); Daniel Lokshtanov (UC)
Paper | Long talk | Session | Poster
15:00 Coded trace reconstruction in a constant number of traces
Joshua Brakensiek (Stanford ); Ray Li (Stanford ); Bruce Spang (Stanford )
Paper | Long talk | Session | Poster
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 | Session | Poster
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 | Session | Poster
15:15 Network Coding Gaps for Completion Times of Multiple Unicasts
Bernhard Haeupler (CMU); David Wajc (CMU); Goran Zuzic (CMU)
Paper | Long talk | Session | Poster
Maximizing Determinants under Matroid Constraints
Vivek Madan (Amazon); Aleksandar Nikolov (Univ. of Toronto); Mohit Singh (Georgia Tech); Uthaipon Tantipongpipat (Twitter)
Paper | Long talk | Session | Poster
16:00 Reports Session and Award Presentations
Poster Sessions
24:00 Session 4A Session 4B Session 4C
Wednesday, November 18
Session 5A Session 5B Session 5C
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 | Session | Poster
Lazy Search Trees.
Bryce Sandlund (Waterloo); Sebastian Wild (Liverpool)
Paper | Long talk | Session | Poster
New Techniques for Proving Fine-Grained Average-Case Hardness.
Mina Dalirrooyfard (MIT); Andrea Lincoln (MIT); Virginia Vassilevska Williams (MIT)
Paper | Long talk | Session | Poster
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 | Session | Poster
2D Fractional Cascading on Axis-aligned Planar Subdivisions.
Peyman Afshani (Aarhus); Pingan Cheng (Aarhus)
Paper | Long talk | Session | Poster
Monochromatic Triangles, Triangle Listing and APSP.
Virginia Williams (MIT); Yinzhan Xu (MIT)
Paper | Long talk | Session | Poster
11:30 Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs.
Mančinska (Copenhagen); David E. Roberson (Technical Univ., Denmark)
Paper | Long talk | Session | Poster
Subsets and Supermajorities: Optimal Hashing-based Set Similarity Search.
Thomas Ahle (BARC, IT Univ. Copenhagen); Jakob Knudsen (BARC, Univ. Copenhagen)
Paper | Long talk | Session | Poster
A Parameterized Approximation Scheme for Min k-Cut
Daniel Lokshtanov (UC); Saket Saurabh (IMS, HBNI); Vaishali Surianarayanan (UC)
Paper | Long talk | Session | Poster
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 | Session | Poster
Polynomial Data Structure Lower Bounds in the Group Model.
Alexander Golovnev (Harvard); Gleb Posobin (Columbia); Oded Regev (NYU); Omri Weinstein (Columbia)
Paper | Long talk | Session | Poster
Hypergraph k-cut for fixed k in deterministic polynomial time.
Karthekeyan Chandrasekaran (UIUC); Chandra Chekuri (UIUC)
Paper | Long talk | Session | Poster
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 | Session | Poster
An Adaptive Step Toward the Multiphase Conjecture and Lower Bounds on Nonlinear Networks.
Young Kun Ko (NYU); Omri Weinstein (Columbia)
Paper | Long talk | Session | Poster
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 | Session | Poster
12:15 Entanglement Is Necessary for Optimal Quantum Property Testing.
Sebastien Bubeck (MSR); Sitan Chen (MIT); Jerry Li (MSR)
Paper | Long talk | Session | Poster
Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations.
Ariel Kulik (Technion); Hadas Shachnai (Technion)
Paper | Long talk | Session | Poster
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 | Session | Poster
Session 6A Session 6B Session 6C
14:00 Local Proofs Approaching the Witness Length.
Noga Ron-Zewi (Haifa); Ron Rothblum (Technion)
Paper | Long talk | Session | Poster
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 | Session | Poster
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 | Session | Poster
14:15 Rigid Matrices from Rectangular PCPs.
Amey Bhangale (UC ); Prahladh Harsha (TIFR); Orr Paradise (UC Berkeley); Avishay Tal (UC Berkeley)
Paper | Long talk | Session | Poster
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 | Session | Poster
Edit Distance in Near-Linear Time: it’s a Constant Factor.
Alexandr Andoni (Columbia); Negev Shekel Nosatzki (Columbia)
Paper | Long talk | Session | Poster
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 | Session | Poster
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 | Session | Poster
Resolution of the Burrows-Wheeler Transform Conjecture.
Dominik Kempa (UC Berkeley); Tomasz Kociumaka (Bar-Ilan Univ.)
Paper | Long talk | Session | Poster
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 | Session | Poster
Subexponential LPs Approximate Max-Cut.
Samuel Hopkins (UC Berkeley); Tselil Schramm (Stanford); Luca Trevisan (Bocconi Univ.)
Paper | Long talk | Session | Poster
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 | Session | Poster
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 | Session | Poster
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 | Session | Poster
Smoothing the gap between NP and ER.
Jeff Erickson (UIUC); Ivor van der Hoog (Utrecht Univ.); Tillmann Miltzow (Utrecht Univ.)
Paper | Long talk | Session | Poster
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 | Session | Poster
Approximation Algorithms for Stochastic Minimum Norm Combinatorial Optimization.
Sharat Ibrahimpur (Waterloo); Chaitanya Swamy (Waterloo)
Paper | Long talk | Session | Poster
Point Location and Active Learning: Learning Halfspaces Almost Optimally.
Max Hopkins (UC); Daniel Kane (UC); Shachar Lovett (UC); Gaurav Mahajan (UC)
Paper | Long talk | Session | Poster
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 Session 7B Session 7C
11:00 Explicit near-fully X-Ramanujan graphs.
Ryan O’Donnell (CMU); Xinyu Wu (CMU)
Paper | Long talk | Session | Poster
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 | Session | Poster
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance.
Tomasz Kociumaka (Bar-Ilan Univ.); Barna Saha (UC Berkeley)
Paper | Long talk | Session | Poster
11:15 Nearly Optimal Pseudorandomness From Hardness.
Dean Doron (Stanford); Dana Moshkovitz (UT); Justin Oh (UT); David Zuckerman (UT)
Paper | Long talk | Session | Poster
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 | Session | Poster
Testing linear-invariant properties.
Jonathan Tidor (MIT); Yufei Zhao (MIT)
Paper | Long talk | Session | Poster
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 | Session | Poster
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 | Session | Poster
Testing Positive Semi-Definiteness via Random Submatrices.
Ainesh Bakshi (CMU); Nadiia Chepurko (MIT); Rajesh Jayaram (CMU)
Paper | Long talk | Session | Poster
11:45 An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature.
Andrew Drucker (Univ. of Chicago)
Paper | Long talk | Session | Poster
Fully-Dynamic Submodular Cover with Bounded Recourse.
Anupam Gupta (CMU); Roie Levin (CMU)
Paper | Long talk | Session | Poster
Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time.
Mahdi Cheraghchi (UM); Vasileios Nakos (Saarland Univ.)
Paper | Long talk | Session | Poster
12:00 A Dichotomy for Real Boolean Holant Problems.
Shuai Shao (UW-Madison); Jin-Yi Cai (UW-Madison)
Paper | Long talk | Session | Poster
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 | Session | Poster
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 | Session | Poster
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 | Poster
Session 8A Session 8B Session 8C
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 | Long talk | Session | Poster
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 | Session | Poster
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 | Session | Poster
14:15 On One-way Functions and Kolmogorov Complexity.
Yanyi Liu (Cornell); Rafael Pass (Cornell Tech)
Paper | Long talk | Session | Poster
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction.
Zongchen Chen (Georgia Tech); Kuikui Liu (UW); Eric Vigoda (Georgia Tech)
Paper | Long talk | Session | Poster
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 | Session | Poster
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 | Session | Poster
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 | Session | Poster
Stochastic Weighted Matching: $(1-\epsilon)$ Approximation.
Soheil Behnezhad (UMD); Mahsa Derakhshan (UMD)
Paper | Long talk | Session | Poster
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 | Session | Poster
Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases.
Nima Anari (Stanford); Michal Derezinski (UC-Berkeley)
Paper | Long talk | Session | Poster
Optimal anytime regret with two experts.
Nicholas Harvey (UBC); Christopher Liaw (UBC); Edwin Perkins (UBC); Sikander Randhawa (UBC)
Paper | Long talk | Session | Poster
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 | Session | Poster
The complexity of approximating averages on bounded-degree graphs.
Andreas Galanis (Oxford); Daniel Stefankovic (Univ. of Rochester); Eric Vigoda (Georgia Tech)
Paper | Long talk | Session | Poster
AdWords in a Panorama.
Zhiyi Huang (HKU); Qiankun Zhang (HKU); Yuhao Zhang (HKU)
Paper | Long talk | Session | Poster
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 | Session | Poster
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 | Session | Poster
Resolving the Optimal Metric Distortion Conjecture.
Vasilis Gkatzelis (Drexel); Daniel Halpern (Univ. of Toronto); Nisarg Shah (Univ. of Toronto)
Paper | Long talk | Session | Poster
Poster Sessions
24:00 Session7A Session 7B Session 7C Session 8A Session 8B Session 8C
FOCS 2020 concludes