The times listed in this table are in Central European Time.
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 2021 Program
Monday, June 21
Session 1A, Room A
Chair: Ankur Moitra
Session 1B, Room B
Chair: Eric Allender
Session 1C, Room C
Chair: Liam Roditty
15:00
Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design (Video)
Yufei Ruan (University of Illinois at Urbana-Champaign); Jiaqi Yang (Tsinghua University); Yuan Zhou (University of Illinois at Urbana-Champaign)
Log-Rank and Lifting for AND-Functions (Video)
Alexander Knop, Shachar Lovett, Sam McGuire (UCSD); Weiqiang Yuan (Tsinghua University)
Vertex Connectivity in Poly-logarithmic Max-Flows (Video)
Jason Li (Carnegie Mellon University); Danupon Nanongkai (KTH Royal Institute of Technology); Debmalya Panigrahi (Duke University); Thatchaphol Saranurak (Toyota Technological Institute at Chicago); Sorrachai Yingchareonthawornchai (Aalto University)
15:12
Efficiently Learning Halfspaces with Tsybakov Noise (Video)
Ilias Diakonikolas (UW Madison); Daniel M. Kane (UCSD); Vasilis Kontonis, Christos Tzamos, Nikos Zarifis (UW Madison)
Automating Algebraic Proof Systems Is NP-Hard (Video)
Susanna F. de Rezende (Institute of Mathematics of the Czech Academy of Sciences); Mika Göös (EPFL); Jakob Nordström (University of Copenhagen & Lund University); Toniann Pitassi (University of Toronto & IAS); Robert Robere (McGill University); Dmitry Sokolov (St. Petersburg State University & PDMI RAS)
Finding Large Induced Sparse Subgraphs in $C_{>t}$-Free Graphs in Quasipolynomial Time (Video)
Peter Gartland, Daniel Lokshtanov (University of California at Santa Barbara, USA); Marcin Pilipczuk, Michał Pilipczuk (University of Warsaw, Poland); Paweł Rzążewski (Warsaw University of Technology and University of Warsaw, Poland)
15:24
Robust Linear Regression: Optimal Rates in Polynomial Time (Video)
Ainesh Bakshi, Adarsh Prasad (Carnegie Mellon University)
Strong Co-nondeterministic Lower Bounds for NP Cannot Be Proved Feasibly (Video)
Jan Pich, Rahul Santhanam (University of Oxford)
Clan Embeddings into Trees, and Low Treewidth Graphs (Video)
Arnold Filtser (Columbia University); Hung Le (University of Massachusetts, Amherst)
15:36
Statistical Query Complexity of Manifold Estimation (Video)
Eddie Aamari (Sorbonne Université, Université de Paris, CNRS); Alexander Knop (UCSD)
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity (Video)
Rahul Santhanam (University of Oxford); Iddo Tzameret (Imperial College London)
Tree Embeddings for Hop-Constrained Network Design (Video)
Bernhard Haeupler, D Ellis Hershkowitz (Carnegie Mellon University); Goran Zuzic (ETH Zurich)
15:48
When Is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning? (Video)
Gavin Brown, Mark Bun (Boston University); Vitaly Feldman (Apple); Adam Smith (Boston University); Kunal Talwar (Apple)
New Separations Results for External Information (Video)
Mark Braverman (Princeton University); Dor Minzer (MIT)
Bridging the Gap between Tree and Connectivity Augmentation: Unified and Stronger Approaches (Video)
Federica Cecchetto, Vera Traub, Rico Zenklusen (ETH Zurich)
16:00 Break
16:15
Tutorial 1: Log-concave polynomials in theory and applications
Organizers: Nima Anari (Stanford) and Cynthia Vinzant (NCSU / University of Washington)
Chair: Ryan O'Donnell (CMU)
Room A
Tutorial 2: Statistical physics of random CSPs
Organizers: Nike Sun, MIT
Chair: Leonard Schulman (Caltech)
Room B
18:15 Junior/Senior Lunches - Lounge
Best Student Papers - Auditorium (Video)
19:15
Discrepancy Minimization via a Self-Balancing Walk (Video)
Ryan Alweiss (Princeton University), Yang P. Liu (Stanford University), and Mehtaab Sawhney (Massachusetts Institute of Technology)
19:35
Separating Words and Trace Reconstruction (Video)
Zachary Chase (University of Oxford)
Best Papers - Auditorium (Video)
19:55
A (Slightly) Improved Approximation Algorithm for Metric TSP (Video)
Anna R. Karlin (University of Washington), Nathan Klein (University of Washington), and Shayan Oveis Gharan (University of Washington)
20:15
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS (Video)
John Fearnley (University of Liverpool), Paul W. Goldberg (University of Oxford), Alexandros Hollender (University of Oxford), and Rahul Savani (University of Liverpool)
20:35
Indistinguishability Obfuscation from Well-Founded Assumptions (Video)
Aayush Jain (University of California at Los Angeles), Huijia Lin (University of Washington), and Amit Sahai (University of California at Los Angeles)
21:00 Break
Session 2A, Room A
Chair: Guy Rothblum
Session 2B, Room B
Chair: Avishay Tal
Session 2C, Room C
Chair: Michael Dinitz
21:15
Sample-Optimal and Efficient Learning of Tree Ising Models (Video)
Constantinos Daskalakis, Qinxuan Pan (MIT)
AND
Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu (Video)
Arnab Bhattacharyya, Sutanu Gayen (National University of Singapore); Eric Price (The University of Texas at Austin); N. V. Vinodchandran (University of Nebraska-Lincoln)
Polynomial Time Deterministic Identity Testing Algorithm for Σ [3] ΠΣΠ [2] Circuits via Edelstein–Kelly Type Theorem for Quadratic Polynomials (Video)
Shir Peleg (Tel Aviv University); Amir Shpilka (Tel-Aviv University)
Subcubic Algorithms for Gomory–Hu Tree in Unweighted Graphs (Video)
Amir Abboud (IBM Almaden Research Center); Robert Krauthgamer, Ohad Trabelsi (Weizmann Institute of Science)
21:27
Learning Ising Models from One or Multiple Samples (Video)
Yuval Dagan, Anthimos-Vardis Kandiros (MIT); Constantinos Daskalakis (EECS, MIT); Nishanth Dikkala (Google)
An Improved Derandomization of the Switching Lemma (Video)
Zander Kelley (University of Illinois at Urbana-Champaign)
Support of Closed Walks and Second Eigenvalue Multiplicity of Graphs (Video)
Theo McKenzie (University of California, Berkeley); Peter M. R. Rasmussen (University of Copenhagen); Nikhil Srivastava (UC Berkeley)
21:39
Sample-Efficient Proper PAC Learning with Approximate Differential Privacy (Video)
Badih Ghazi (Google); Noah Golowich (MIT); Ravi Kumar (Google); Pasin Manurangsi (Google Research)
Simple and Fast Derandomization from Very Hard Functions: Eliminating Randomness at Almost No Cost (Video)
Lijie Chen, Roei Tell (Massachusetts Institute of Technology)
Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests (Video)
Nima Anari (Stanford University); Kuikui Liu, Shayan Oveis Gharan (University of Washington); Cynthia Vinzant (North Carolina State University); Thuy-Duong Vuong (Stanford University)
21:51
Local Concentration Inequalities and Tomaszewski’s Conjecture (Video)
Nathan Keller, Ohad Klein (Bar Ilan University)
Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions (Video)
Shuichi Hirahara (National Institute of Informatics)
Breaking the Quadratic Barrier for Matroid Intersection (Video)
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai (KTH Royal Institute of Technology)
22:03
Pseudodeterministic Algorithms and the Structure of Probabilistic Time (Video)
Zhenjian Lu, Igor C. Oliveira (University of Warwick); Rahul Santhanam (University of Oxford)
Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More (Video)
Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, Thuy-Duong Vuong (Stanford University)
22:15 - 23:00 Poster Session (for Sessions 1 and 2) - Poster Room
Tuesday, June 22
15:00
Workshop #1: TCS Women Spotlight Workshop
Organizers: Elena Grigorescu (Purdue), Sofya Raskhodnikova (Boston University), Barna Saha (UC Berkeley), Virginia Vassilevska Williams (MIT), and Mary Wootters (Stanford)
Room A
Workshop #2: The Recent Past and Near Future of Clustering
Organizers: Vincent Cohen-Addad (Google Zürich), Frederik Mallmann-Trenn (King's College London), and Chris Schwiegelshohn (Aarhus University)
Room B
18:00 Theory Trivia - Lounge
18:45
Keynote #1: Go Ask Alice: Advances and Directions in Communication Complexity (Video)
Toniann Pitassi (University of Toronto)
Chair: Ryan O'Donnell (CMU)
Auditorium
19:45 Break
Session 3A, Room A
Chair: Sam Hopkins
Session 3B, Room B
Chair: Artur Czumaj
Session 3C, Room C
Chair: Yael Kalai
20:00
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification (Video)
Noga Alon (Princeton University and Tel Aviv University); Omri Ben-Eliezer (Harvard University); Yuval Dagan (MIT); Shay Moran (Technion); Moni Naor (Weizmann Institute); Eylon Yogev (Tel Aviv University and Boston University)
Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon (Video)
Seth Pettie, Dingyu Wang (University of Michigan)
Continuous LWE (Video)
Joan Bruna, Oded Regev, Min Jae Song (New York University); Yi Tang (University of Michigan)
20:12
Stronger Calibration Lower Bounds via Sidestepping (Video)
Mingda Qiao, Gregory Valiant (Stanford University)
Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability (Video)
Lijie Chen (Massachusetts Institute of Technology); Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena (Princeton University); Zhao Song (School of Mathematics, IAS); Huacheng Yu (Princeton University)
SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE (Video)
Ruta Jawale (University of Illinois at Urbana-Champaign); Yael Tauman Kalai (Microsoft Research, Massachusetts Institute of Technology); Dakshita Khurana (University of Illinois at Urbana-Champaign); Rachel Zhang (Massachusetts Institute of Technology)
20:24
Hardness of Learning DNFs using Halfspaces (Video)
Suprovat Ghoshal (Indian Institute of Science); Rishi Saket (IBM Research)
Robust Testing of Low Dimensional Functions (Video)
Anindya De (University of Pennsylvania); Elchanan Mossel (MIT); Joe Neeman (University of Texas, Austin)
Cryptography from Sublinear-Time Hardness of Time-Bounded Kolmogorov Complexity (Video)
Yanyi Liu, Rafael Pass (Cornell University)
20:36
Boosting Simple Learners (Video)
Noga Alon (Princeton University); Alon Gonen (OrCam); Elad Hazan (Princeton); Shay Moran (Technion)
Towards Tight Bounds for Spectral Sparsification of Hypergraphs (Video)
Michael Kapralov (EPFL); Robert Krauthgamer (Weizmann Institute of Science); Jakab Tardos (EPFL); Yuichi Yoshida (National Institute of Informatics)
Indistinguishability Obfuscation from Circular Security (Video)
Romain Gay (IBM Research Zurich); Rafael Pass (Cornell Tech)
20:48
Algorithmic Foundations for the Diffraction Limit (Video)
Sitan Chen, Ankur Moitra (MIT)
Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma (Video)
Sepehr Assadi, Vishvajeet N (Rutgers University)
Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW Is Not Zero-Knowledge) (Video)
Justin Holmgren (NTT Research); Alex Lombardi (MIT); Ron Rothblum (Technion)
21:00 Break
Session 4A, Room A
Chair: Tselil Schramm
Session 4B, Room B
Chair: Max Probst Gutenberg
Session 4C, Room C
Chair: Chris Umans
21:15
VC Dimension and Distribution-Free Sample-Based Testing (Video)
Eric Blais, Renato Ferreira Pinto, Jr., Nathaniel Harms (University of Waterloo)
Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time (Video)
Julia Chuzhoy (Toyota Technological Institute at Chicago)
Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma (Video)
Lijie Chen (Massachusetts Institute of Technology); Xin Lyu (Tsinghua University)
21:27
Settling the Robust Learnability of Mixtures of Gaussians (Video)
Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT)
Improved Dynamic Algorithms for Longest Increasing Subsequence (Video)
Tomasz Kociumaka (UC Berkeley); Saeed Seddighin (Toyota Technological Institute at Chicago)
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity (Video)
Josh Alman (Harvard)
21:39
A Theory of Universal Learning (Video)
Olivier Bousquet (Google, Brain Team); Steve Hanneke (TTIC); Shay Moran (Technion); Ramon van Handel (Princeton University); Amir Yehudayoff (Technion)
Fully Dynamic Approximation of LIS in Polylogarithmic Time (Video)
Pawel Gawrychowski, Wojciech Janczewski (University of Wrocław)
Lower Bounds for Monotone Arithmetic Circuits via Communication Complexity (Video)
Arkadev Chattopadhyay (Tata Institue of Fundamental Research); Rajit Datta, Partha Mukhopadhyay (Chennai Mathematical Institute)
21:51
Optimal Testing of Discrete Distributions with High Probability (Video)
Ilias Diakonikolas (UW Madison); Themis Gouleakis (MPI, Germany); Daniel M. Kane (UCSD); John Peebles (Princeton University); Eric Price (UT Austin)
A Framework for Dynamic Matching in Weighted Graphs (Video)
Zachary Langley, Aditi Dudeja, Aaron Bernstein (Rutgers University)
Structure vs. Randomness for Bilinear Maps (Video)
Guy Moshkovitz (City University of New York); Alex Cohen (Yale University)
22:03
Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program (Video)
Zhiyi Huang, Xinkai Shu (The University of Hong Kong)
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits (Video)
Vishwas Bhargava, Shubhangi Saraf (Rutgers University); Ilya Volkovich (Boston College)
22:15 - 23:00 Poster Session (for Sessions 3 and 4) - Poster Room
Wednesday, June 23
15:00
Keynote #2: Legal theorems: bridging computer science and privacy law (Video)
Kobbi Nissim (Georgetown University)
Chair: Salil Vadhan (Harvard)
Auditorium
16:00 Break
16:15
50th Anniversary of the Cook-Levin Theorem (Video)
Participants: Stephen A. Cook (University of Toronto), Richard M. Karp (UC Berkeley), Leonid A. Levin (Boston University), Christos H. Papadimitriou (Columbia University), Avi Wigderson (Institute for Advanced Study)
Chairs: Christos H. Papadimitriou (Columbia University) and Avi Wigderson (Institute for Advanced Study)
Auditorium
18:00 Business Meeting - Auditorium
19:15 Break
19:20 Godel Prize talk: Complexity Dichotomies for Counting CSPs (Video)
Chair: Daniel Spielman (Yale)
Auditorium
19:45 Break
Mini-Plenaries (Session 1)
Chair: Cris Moore (Sante Fe Institute)
Auditorium
20:00
Talk #1: Neural Tangent Kernel: Convergence and Generalization in Neural Networks (Video)
Arthur Jacot, Franck Gabriel, Clément Hongler
20:25
Talk #2: Learnability can be undecidable (Video)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
20:50
Talk #3: Chasing Convex Bodies with Linear Competitive Ratio (Video)
C. J. Argue, Anupam Gupta, Guru Guruganesh, Ziye Tang
21:15
Talk #4: A Polynomial-Time Approximation Algorithm for Counting Words Accepted by an NFA (Video)
Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros
21:45 Break
Session 5A, Room A
Chair: Aaron Sidford
Session 5B, Room B
Chair: Ruta Mehta
Session 5C, Room C
Chair: Huacheng Yu
22:00
A Faster Algorithm for Solving General LPs (Video)
Shunhua Jiang (Columbia University); Zhao Song (School of Mathematics, IAS); Omri Weinstein, Hengjie Zhang (Columbia University)
The Randomized Communication Complexity of Randomized Auctions (Video)
Aviad Rubinstein; Junyao Zhao (Stanford University)
Reducing Isotropy and Volume to KLS: An O *( n 3 ψ 2 ) Volume Algorithm (Video)
He Jia, Aditi Laddha (Georgia Tech); Yin Tat Lee (University Washington); Santosh Vempala (Georgia Tech)
22:12
Combinatorial Bernoulli Factories: Matchings, Flows, and Other Polytopes (Video)
Rad Niazadeh (University of Chicago Booth School of Business); Renato Paes Leme, Jon Schneider (Google Research)
Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex-Nonconcave Min-Max Optimization (Video)
Oren Mangoubi (WPI); Nisheeth K. Vishnoi (Yale University)
A New Algorithm for Euclidean Shortest Paths in the Plane (Video)
Haitao Wang (Utah State University)
22:24
Capacity Lower Bounds via Productization (Video)
Leonid Gurvits (The City College of New York); Jonathan Leake (TU Berlin)
Contextual Search in the Presence of Irrational Agents (Video)
Akshay Krishnamurthy, Thodoris Lykouris (Microsoft Research NYC); Chara Podimata (Harvard University); Robert Schapire (Microsoft Research NYC)
Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions (Video)
Natan Rubin (Ben-Gurion University)
22:36
Minimum Cost Flows, MDPs, and $\ell_1$-Regression in Nearly Linear Time for Dense Instances (Video)
Jan van den Brand (KTH Royal Institute of Technology); Yin Tat Lee (University Washington); Yang P. Liu (Stanford University); Thatchaphol Saranurak (Toyota Technological Institute at Chicago); Aaron Sidford (Stanford University); Zhao Song (School of Mathematics, IAS); Di Wang (Google)
How Much Data Is Sufficient to Learn High-Performing Algorithms? Generalization Guarantees for Data-Driven Algorithm Design (Video)
Maria-Florina Balcan (Carnegie Mellon University); Dan DeBlasio (University of Texas at El Paso); Travis Dick (University of Pennsylvania); Carl Kingsford, Tuomas Sandholm, Ellen Vitercik (Carnegie Mellon University)
Dynamic Planar Point Location in Optimal Time (Video)
Yakov Nekrich (Michigan Technological University)
22:48
A Framework for Quadratic Form Maximization over Convex Sets through Nonconvex Relaxations (Video)
Vijay Bhattiprolu (IAS/Princeton); Euiwoong Lee (University of Michigan); Assaf Naor (Princeton University)
The Communication Complexity of Payment Computation (Video)
Shahar Dobzinski, Shiri Ron (Weizmann Institute of Science)
AND
Exponential Communication Separations between Notions of Selfishness (Video)
Aviad Rubinstein (Stanford University); Raghuvansh Saxena, Clayton Thomas, S. Matthew Weinberg (Princeton University); Junyao Zhao (Stanford University)
A New Coreset Framework for Clustering (Video)
Vincent Cohen-Addad (Google Research, Switzerland); David Saulpic (Sorbonne Université, Paris); Chris Schwiegelshohn (Aarhus University)
23:00 - 23:30 Poster Session (for Session 5) - Poster Room
Thursday, June 24
15:00
Workshop #3: MIP* = RE
Organizers: Anand Natarajan (MIT) and John Wright (University of Texas)
Room A
Workshop #4: Robust Streaming, Sketching and Sampling
Organizers: Omri Ben-Eliezer (Harvard), Rajesh Jayaram (CMU), and Uri Stemmer (Ben-Gurion University)
Room B
18:00 More theory trivia + conclusion of the mystery hunt - Lounge
18:45
Keynote #3: Quantum supremacy in a programmable superconducting processor (Video)
John Martinis (Silicon Quantum Computing and UC Santa Barbara)
Chair: Leonard Schulman (Caltech)
Auditorium
19:45 Break
Session 6A, Room A
Chair: Mohit Singh
Session 6B, Room B
Chair: Mohsen Ghaffari
Session 6C, Room C
Chair: Thomas Vidick
20:00
When Is Approximate Counting for Conjunctive Queries Tractable? (Video)
Marcelo Arenas, Luis Alberto Croquevielle (PUC & IMFD Chile); Rajesh Jayaram (Carnegie Mellon University); Cristian Riveros (PUC & IMFD Chile)
Distributed Weighted Min-Cut in Nearly-Optimal Time (Video)
Michal Dory (ETH Zurich, Switzerland); Yuval Efron (University of Toronto, Canada); Sagnik Mukhopadhyay, Danupon Nanongkai (KTH Royal Institute of Technology, Sweden)
Fiber Bundle Codes: Breaking the N 1/2 polylog( N ) Barrier for Quantum LDPC Codes (Video)
Matthew Hastings, Jeongwan Haah (Microsoft Research); Ryan O'Donnell (Carnegie Mellon University)
20:12
Near-Linear Time Approximation Schemes for Steiner Tree and Forest in Low-Dimensional Spaces (Video)
Yair Bartal (Hebrew University); Lee-Ad Gottlieb (Ariel University)
A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique (Video)
Krzysztof Nowicki (University of Copenhagen and University of Wrocław)
An Optimal Separation of Randomized and Quantum Query Complexity (Video)
Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu (UCLA)
AND
k-Forrelation Optimally Separates Quantum and Classical Query Complexity (Video)
Nikhil Bansal (CWI Amsterdam and TU Eindhoven); Makrand Sinha (CWI Amsterdam)
20:24
A $(2 + \varepsilon)$-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine (Video)
Lars Rohwedder (EPFL); Andreas Wiese (Universidad de Chile)
Universally-Optimal Distributed Algorithms for Known Topologies (Video)
Bernhard Haeupler (Carnegie Mellon University); David Wajc (Stanford University); Goran Zuzic (ETH Zurich)
New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with Ω(√ n log k n ) Distance (Video)
Tali Kaufman (BIU); Ran J. Tessler (Weizmann Institute of Science)
20:36
A Quasipolynomial (2 + ε)-Approximation for Planar Sparsest Cut (Video)
Vincent Cohen-Addad (Google Research, Switzerland); Anupam Gupta (Carnegie Mellon); Philip N Klein (Brown University); Jason Li (Carnegie Mellon University)
Efficient Randomized Distributed Coloring in CONGEST (Video)
Magnus M. Halldorsson (Reykjavik University); Fabian Kuhn (University of Freiburg); Yannic Maus, Tigran Tonoyan (Technion - Israel Institute of Technology)
Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem (Video)
Scott Aaronson (University of Texas at Austin); Shalev Ben-David (University of Waterloo); Robin Kothari (Microsoft Quantum and Microsoft Research); Shravas Rao (Northwestern University); Avishay Tal (UC Berkeley)
20:48
Flow Time Scheduling with Uncertain Processing Time (Video)
Yossi Azar (Tel Aviv University); Stefano Leonardi (University of Rome La Sapienza); Noam Touitou (Tel Aviv University)
The Communication Complexity of Multiparty Set Disjointness under Product Distributions (Video)
Nachum Dershowitz, Rotem Oshman, Tal Roth (Tel Aviv University)
Eliminating Intermediate Measurements in Space-Bounded Quantum Computation (Video)
Bill Fefferman, Zachary Remscrim (The University of Chicago)
21:00 Break
Session 7A, Room A
Chair: Mark Bun
Session 7B, Room B
Chair: Faith Ellen
Session 7C, Room C
Chair: Avishay Tal
21:15
The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation (Video)
Albert Cheu, Jonathan Ullman (Northeastern University)
Hop-Constrained Oblivious Routing (Video)
Mohsen Ghaffari (ETH Zurich); Bernhard Haeupler (Carnegie Mellon University); Goran Zuzic (ETH Zurich)
(Sub)Exponential Advantage of Adiabatic Quantum Computation with No Sign Problem (Video)
András Gilyén (IQIM, Caltech); Matthew Hastings (Microsoft Research); Umesh Vazirani (U.C. Berkeley)
21:27
Outcome Indistinguishability (Video)
Cynthia Dwork (Harvard University); Michael P. Kim (UC Berkeley); Omer Reingold (Stanford University); Guy N. Rothblum, Gal Yona (Weizmann Institute of Science)
Efficient Randomized DCAS (Video)
George Giakkoupis (INRIA, Rennes); Mehrdad Jafari Giv, Philipp Woelfel (University of Calgary)
Succinct Blind Quantum Computation Using a Random Oracle (Video)
Jiayu Zhang (Boston University)
21:39
Optimal Labelling Schemes for Adjacency, Comparability, and Reachability (Video)
Marthe Bonamy (CNRS, Labri, Université de Bordeaux); Louis Esperet (CNRS, G-SCOP, Univ. Grenoble Alpes); Carla Groenland, Alex Scott (University of Oxford)
Optimal Error Resilience of Adaptive Message Exchange (Video)
Klim Efremenko (Ben-Gurion University); Gillat Kol, Raghuvansh Saxena (Princeton University)
Sampling Matrices from Harish-Chandra–Itzykson–Zuber Densities with Applications to Quantum Inference and Differential Privacy (Video)
Jonathan Leake (TU Berlin); Colin McSwiggen (Brown University); Nisheeth K. Vishnoi (Yale University)
21:51
Bipartite Perfect Matching as a Real Polynomial (Video)
Gal Beniamini, Noam Nisan (The Hebrew University of Jerusalem)
How Asymmetry Helps Buffer Management: Achieving Optimal Tail Size in Cup Games (Video)
William Kuszmaul (MIT)
Improved Quantum Data Analysis (Video)
Costin Bădescu, Ryan O'Donnell (Carnegie Mellon University)
22:03
Efficient and Near-Optimal Algorithms for Sampling Connected Subgraphs (Video)
Marco Bressan (University of Milan)
Load Balancing with Dynamic Set of Balls and Bin (Video)
Anders Aamand, Mikkel Thorup, Jakob Knudsen (University of Copenhagen)
22:15 - 23:00 Poster Session (for Sessions 6 and 7) - Poster Room
Friday, June 25
15:00
Keynote #4: Computational Thinking in Programming Language and Compiler Design (Video)
Alfred V. Aho (Columbia University)
Chair: Tim Roughgarden (Columbia)
Auditorium
16:00 Break
Mini-Plenaries (Session 2)
Chair: Nicole Immorlica (Microsoft Research)
Auditorium
16:15
Talk #1: A New Analysis of Differential Privacy's Generalization Guarantees (Video)
Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, Moshe Shenfeld
16:40
Talk #2: Simplicity Creates Inequity: Implications for Fairness, Stereotypes, and Interpretability (Video)
Jon Kleinberg, Sendhil Mullainathan
17:05
Talk #3: Load Balancing Guardrails: Keeping Your Heavy Traffic on the Road to Low Response Times (Video)
Isaac Grosof, Ziv Scully, Mor Harchol-Balter
17:30
Talk #4: The ghost in the radiation: Robust encodings of the black hole interior (Video)
Isaac H. Kim, Eugene Tang, John Preskill
18:00 Junior/Senior Lunches - Lounge
19:00
Knuth Prize talk: Logic and Computation – A Match Made in Heaven (Video)
Moshe Vardi (Rice University)
Chair: Hal Gabow (University of Colorado)
Auditorium
19:45 Break
Session 8A, Room A
Chair: Inbal Talgam-Cohen
Session 8B, Room B
Chair: Aravindan Vijayaraghavan
Session 8C, Room C
Chair: Virginia Vassilevska Williams
20:00
Approximating Nash Social Welfare under Rado Valuations (Video)
Jugal Garg (University of Illinois at Urbana-Champaign); Edin Husić, László A. Végh (Department of Mathematics, London School of Economics)
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion (Video)
Zongchen Chen (Georgia Institute of Technology); Kuikui Liu (University of Washington); Eric Vigoda (Georgia Institute of Technology)
Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors (Video)
Jesper Nederlof (Utrecht University); Karol Wegrzycki (Saarland University and Max Planck Institute for Informatics)
20:12
Settling the Complexity of Nash Equilibrium in Congestion Games (Video)
Yakov Babichenko (Technion, Faulty of Industrial Engineering and Management); Aviad Rubinstein (Stanford)
Entropy Decay in the Swendsen-Wang Dynamics on ℤ d (Video)
Antonio Blanca (Penn State); Pietro Caputo, Daniel Parisi (University of Roma Tre); Alistair Sinclair (U.C. Berkeley); Eric Vigoda (Georgia Tech)
Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH) (Video)
Ray Li (Stanford University)
AND
Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs (Video)
Mina Dalirrooyfard, Nicole Wein (MIT)
20:24
Revelation Gap for Pricing from Samples (Video)
Yiding Feng, Jason Hartline, Yingkai Li (Northwestern University)
Sampling Constraint Satisfaction Solutions in the Local Lemma Regime (Video)
Weiming Feng (Nanjing University); Kun He (ICT,CAS); Yitong Yin (Nanjing University)
Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution (Video)
Karl Bringmann, Nick Fischer, Vasileios Nakos (Saarland University and Max Planck Institute for Informatics)
20:36
Efficient Two-Sided Markets with Limited Information (Video)
Paul Duetting (Google Research); Federico Fusco, Philip Lazos, Stefano Leonardi, Rebecca Reiffenhauser (Sapienza University of Rome)
Frozen 1-RSB Structure of the Symmetric Ising Perceptron (Video)
Will Perkins (University of Illinois Chicago); Changji Xu (Harvard University)
Deterministic Mincut in Almost-Linear Time (Video)
Jason Li (Carnegie Mellon University)
20:48
The Complexity of Constrained Min-Max Optimization (Video)
Constantinos Daskalakis (EECS, MIT); Stratis Skoulakis (ESD, SUTD); Manolis Zampetakis (UC Berkeley)
Perfectly Sampling k ≥ (8/3 + o (1))Δ-Colorings in Graphs (Video)
Vishesh Jain (Simons Institute for the Theory of Computing); Ashwin Sah, Mehtaab Sawhney (MIT)
Approximate Gomory–Hu Tree Is Faster Than $n-1$ Max-Flows (Video)
Jason Li (Carnegie Mellon University); Debmalya Panigrahi (Duke University)
21:00 Break
Session 9A, Room A
Chair: Mary Wootters
Session 9B, Room B
Chair: Dor Minzer
Session 9C, Room C
Chair: Fedor Fomin
21:15
On Codes Decoding a Constant Fraction of Errors on the BSC (Video)
Jan Hązła (EPFL); Alex Samorodnitsky (Hebrew University); Ori Sberlo (Tel-Aviv University)
The Metric Relaxation for $0$-Extension Admits an $\Omega(\log^{\frac{2}{3}}{k})$ Gap (Video)
Roy Schwartz, Nitzan Tur (Technion)
Constant Approximating k-Clique Is W[1]-Hard (Video)
Bingkai Lin (Nanjing University)
21:27
Decoding Multivariate Multiplicity Codes on Product Sets (Video)
Siddharth Bhandari, Prahladh Harsha (Tata Institute of Fundamental Research); Mrinal Kumar (IIT Bombay); Madhu Sudan (Harvard)
Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups (Video)
Amey Bhangale (University of California, Riverside); Subhash Khot (New York University)
Vertex Deletion Parameterized by Elimination Distance and Even Less (Video)
Bart M. P. Jansen, Jari J. H. de Kroon, Michał Włodarczyk (Eindhoven University of Technology)
21:39
Efficient List-Decoding with Constant Alphabet and List Sizes (Video)
Zeyu Guo, Noga Ron-Zewi (University of Haifa)
Playing Unique Games on Certified Small-Set Expanders (Video)
Mitali Bafna, Boaz Barak (Harvard); Pravesh Kothari (CMU); Tselil Schramm (Stanford); David Steurer (ETH Zurich)
A Full Complexity Dichotomy for Immanant Families (Video)
Radu Curticapean (IT University of Copenhagen, Basic Algorithms Research Copenhagen)
21:51
Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity (Video)
Jad Silbak (Tel Aviv University); Ronen Shaltiel (University of Haifa)
Expander Random Walks: A Fourier-Analytic Approach (Video)
Gil Cohen, Noam Peri, Amnon Ta-Shma (Tel Aviv University)
A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path (Video)
Sally Dong, Yin Tat Lee, Guanghao Ye (University of Washington)
22:03
Near-Linear Time Decoding of Ta-Shma’s Codes via Splittable Regularity (Video)
Fernando Granha Jeronimo (University of Chicago); Shashank Srivastava, Madhur Tulsiani (TTIC)
22:15 - 23:00 Poster Session (for Sessions 8 and 9) - Poster Room
The times listed in this table are in Central European Time .