ITCS 2021 Program and Schedule

Welcome to ITCS 2021. The conference is virtual, being hosted on the Simons Institute map, where you can meet and chat with other attendees and access both Lecture Rooms (Room A and Room B). The sessions will take place as Zoom webinars and can also be accessed via the links in the schedule below.

Registration: In order to have the option to be seen/heard during the sessions, you must register here. Note that registration is free, and it is intended that all participants should register.

Session and talk format: Each session is one hour long, composed of five (with a few exceptions) 8-minute live presentations. Following the presentations, there is a 20-minute "panel discussion" period whose format is decided by the session chair. This is an opportunity for the audience to ask questions, or for the chair to facilitate a discussion among the speakers. The sessions generally alternate between Room A and Room B so that if panel discussions run long, they don't cut into the next session.

Graduating bits: As is tradition at ITCS, there will be a "Graduating Bits (GB)" session intended for conference participants who are near to graduation (on either side) and wish to present their results, research, plans, personality, etc. This will take place at 09:30AM on January 7th (in the second session of the day). If you wish to participate, contact the GB organizer Gautam Kamath ( as soon as possible. In your email, please include basic information (year or intended year of graduation, university, PhD advisor, thesis topic).

Code of conduct: ITCS is committed to an inclusive conference experience, respectful of all participants, and free from any discrimination or harassment, including unwelcome advances or propositions of an intimate nature, particularly when coming from a more senior researcher to a less senior one. All ITCS attendees are expected to behave accordingly. If you experience or witness discrimination, harassment or other unethical behavior at the conference, we encourage you to seek advice and remedy.

In the schedule below, you can find recorded videos of longer presentations. You can join the ITCS 2021 slack by clicking here. There is a slack channel associated to every paper where one can ask questions or enter discussions with the authors and other conference attendees. All times are in PST (California time zone).

January 6th

Room A
Introductory remarks
Crypto and Privacy
Room A
Chair: Elette Boyle
On Distributed Differential Privacy and Counting Distinct Elements [video | slack]
Lijie Chen (MIT), Badih Ghazi (Google), Ravi Kumar (Google), Pasin Manurangsi (Google)
On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions [video | slack]
Mikito Nanashima (Tokyo Institute of Technology)
Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists) [video | slack]
Noga Ron-Zewi (University of Haifa), Ronen Shaltiel (University of Haifa), Nithin Varma (University of Haifa)
Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma [video | slack]
Stefan Dziembowski (University of Warsaw), Grzegorz Fabiański (University of Warsaw), Sebastian Faust (TU Darmstadt), Siavash Riahi (TU Darmstadt)
Black-Box Uselessness: Composing Separations in Cryptography [video | slack]
Geoffroy Couteau (CNRS & IRIF), Pooya Farshim (University of York), Mohammad Mahmoody (University of Virginia)
Distributed models
Room B
Chair: Leonard Schulman
Distributed load balancing: a new framework and improved guarantees [video | slack]
Allen Liu (MIT), Sara Ahmadian (Google), Binghui Peng (Columbia University), Morteza Zadimoghaddam (Google Research)
A Generalized Matching Reconfiguration Problem [video | slack]
Noam Solomon (Tel Aviv University and Immunai), Shay Solomon (Tel Aviv University)
Sequential Defaulting in Financial Networks [video | slack]
Pál András Papp (ETH Zurich), Roger Wattenhofer (ETH Zurich)
The Variable-Processor Cup Game [video | slack]
Alek Westover (MIT), William Kuszmaul (MIT)
A New Model for Ant Trail Formation and its Convergence Properties [video | slack]
Moses Charikar (Stanford University), Shivam Garg (Stanford University), Deborah M. Gordon (Stanford University), Kirankumar Shiragur (Stanford University)
Room A
Chair: Matt Weinberg
Batching and Optimal Multi-stage Bipartite Allocations [video | slack]
Yiding Feng (Northwestern University), Rad Niazadeh (University of Chicago Booth School of Business)
Tiered Random Matching Markets: Rank is Proportional to Popularity [video | slack]
Itai Ashlagi (Stanford University), Mark Braverman (Princeton University), Clayton Thomas (Princeton University), Geng Zhao (Stanford University)
Randomness and Fairness in Two-Sided Matching with Limited Interviews [video | slack]
Hedyeh Beyhaghi (Toyota Technological Institute at Chicago), Eva Tardos (Cornell University)
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets [video | slack]
Vijay Vazirani (University of California, Irvine), Mihalis Yannakakis (Columbia University)
Analytic methods
Room B
Chair: Avishay Tal
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality [video | slack]
Esty Kelman (Tel Aviv University), Subhash Khot (NYU), Guy Kindler (Hebrew University), Dor Minzer (MIT), Muli Safra (Tel-Aviv University)
The Strongish Planted Clique Hypothesis and Its Consequences [video | slack]
Pasin Manurangsi (Google Research), Aviad Rubinstein (Stanford), Tselil Schramm (Stanford)
Ordered Graph Limits and Their Applications [video | slack]
Omri Ben-Eliezer (Harvard University), Eldar Fischer (Technion - Israel Institute of Technology), Amit Levi (University of Waterloo), Yuichi Yoshida (National Institute of Informatics)
Pseudobinomiality of the Sticky Random Walk [video | slack]
Venkatesan Guruswami (CMU), Vinayak Kumar (California Institute of Technology)
On Rich 2-to-1 Games [video | slack]
Mark Braverman (Princeton University), Subhash Khot (NYU), Dor Minzer (MIT)
12:30-13:30 BREAK
Room A
Chair: Luca Trevisan
Explicit SoS lower bounds from high-dimensional expanders [video | slack]
Irit Dinur (Weizmann Institute of Science), Yuval Filmus (Technion), Prahladh Harsha (TIFR), Madhur Tulsiani (Toyota Technological Institute at Chicago)
Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines [video | slack]
Kunal Mittal (Princeton University), Ran Raz (Princeton University)
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs [video | slack]
William Hoza (University of Texas at Austin), Edward Pyne (Harvard University), Salil Vadhan (Harvard University)
Comparing computational entropies below majority (or: When is the dense model theorem false?) [video | slack]
Russell Impagliazzo (University of California, San Diego), Sam McGuire (University of California, San Diego)
Shrinkage under random projections, and cubic formula lower bounds in AC^0 [video | slack]
Yuval Filmus (Technion), Or Meir (University of Haifa), Avishay Tal (UC Berkeley)
Computational complexity
Room B
Chair: Aviad Rubenstein
Total Functions in the Polynomial Hierarchy [video | slack]
Daniel Mitropolsky (Columbia University), Christos Papadimitriou (Columbia University), Robert Kleinberg (Cornell University)
The Complexity of Finding Fair Independent Sets in Cycles [video | slack]
Ishay Haviv (The Academic College of Tel Aviv-Yaffo)
Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution [video | slack]
Olaf Beyersdorff (University of Jena), Benjamin Böhm (University of Jena)
Complete Problems for Multi-Pseudodeterministic Computations [video | slack]
Peter Dixon (Iowa State University), A Pavan (Iowa State University), N. V. Vinodchandran (University of Nebraska-Lincoln)
Two combinatorial MA-complete problems [video | slack]
Dorit Aharonov (Hebrew University of Jerusalem), Alex B. Grilo (CWI and QuSoft)
Room A

January 7th

Room B
Chair: Andris Ambainis
Bounds on the QAC0 Complexity of Approximating Parity [video | slack]
Best Student Paper Award
Gregory Rosenthal (University of Toronto)
Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines [video | slack]
Zachary Remscrim (The University of Chicago)
Time-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers [video | slack]
Abhijit Mudigonda (None), Ryan Williams (MIT)
Self-testing of a single quantum device under computational assumptions [video | slack]
Tony Metger, Thomas Vidick (California Institute of Technology)
Distributed Quantum Proofs for Replicated Data [video | slack]
Pierre Fraigniaud (CNRS and University Paris Diderot), François Le Gall (Nagoya University), Harumichi Nishimura (Nagoya University), Ami Paz (University of Vienna)
Room A
Algorithmic game theory
Room B
Chair: Kira Goldner
How to Sell Information Optimally: an Algorithmic Study [video | slack]
Yang Cai (Yale University), Grigoris Velegkas (Yale University)
Buying Data Over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions [video | slack]
Nicole Immorlica (Microsoft Research), Ian Kash (UIC), Brendan Lucier (Microsoft Research)
Algorithmic Persuasion with Evidence [video | slack]
Martin Hoefer (Goethe University Frankfurt), Pasin Manurangsi (Google Research), Alexandros Psomas (Purdue University)
Non-quasi-linear Agents in Quasi-linear Mechanisms [video | slack]
Moshe Babaioff (Microsoft Research), Richard Cole (NYU), Jason Hartline (Northwestern University), Nicole Immorlica (Microsoft Research), Brendan Lucier (Microsoft Research)
Room A
Chair: Sam Hopkins
Circular Trace Reconstruction [video | slack]
Shyam Narayanan (Massachusetts Institute of Technology), Michael Ren (Massachusetts Institute of Technology)
Sampling Arborescences in Parallel [video | slack]
Nima Anari (Stanford University), Nathan Hu (Stanford University), Amin Saberi (Stanford University), Aaron Schild (University of Washington)
Polynomial-time trace reconstruction in the low deletion rate regime [video | slack]
Xi Chen (Columbia University), Anindya De (University of Pennsylvania), Chin Ho Lee (Columbia University), Rocco A. Servedio (Columbia University), Sandip Sinha (Columbia University)
A New Connection Between Node and Edge Depth Robust Graphs [video | slack]
Jeremiah Blocki (Purdue University), Mike Cinkoske (UIUC)
Algorithms and Hardness for Multidimensional Range Updates and Queries [video | slack]
Joshua Lau, Angus Ritossa (UNSW Sydney)
12:30-13:30 Virtual coffee break in
Graph algorithms
Room A
Chair: Anindya De
Comparison Graphs: a Unified Method for Uniformity Testing [video | slack]
Uri Meir (Tel Aviv University)
Is the space complexity of planted clique recovery the same as that of detection? [video | slack]
Jay Mardia (Stanford University)
An O(n) time algorithm for finding Hamilton cycles with high probability [video | slack]
Rajko Nenadov, Angelika Steger (ETH Zürich), Pascal Su (ETH Zürich)
Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming! [video | slack]
Anup Bhattacharya (Indian Statistical Institute, Kolkata, India), Arijit Bishnu (Indian Statistical Institute, Kolkata, India), Gopinath Mishra (Indian Statistical Institute, Kolkata, India), Anannya Upasana (Indian Statistical Institute, Kolkata, India)
Erasure-Resilient Sublinear-Time Graph Algorithms [video | slack]
Amit Levi (University of Waterloo), Ramesh Krishnan S. Pallavoor (Boston University), Sofya Raskhodnikova (Boston University), Nithin Varma (University of Haifa)
Quantum information
Room B
Chair: Anand Natarajan
Robust Quantum Entanglement at (nearly) Room Temperature [video | slack]
Lior Eldar (None)
The Quantum Supremacy Tsirelson Inequality [video | slack]
William Kretschmer (University of Texas at Austin)
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits [video | slack]
Boaz Barak (Harvard University), Chi-Ning Chou (Harvard University), Xun Gao (Harvard University)
Sample efficient identity testing and independence testing of quantum states [video | slack]
Nengkun Yu (UTS)
Quantum versus Randomized Communication Complexity, with Efficient Players [video | slack]
Uma Girish (Princeton University), Ran Raz (Princeton University), Avishay Tal (UC Berkeley)
Circuits and communication
Room A
Chair: Avishay Tal
Quantitative Correlation Inequalities via Semigroup Interpolation [video | slack]
Shivam Nadimpalli (Columbia University), Rocco A. Servedio (Columbia University), Anindya De (University of Pennsylvania)
Circuit Depth Reductions [video | slack]
Alexander Golovnev (Georgetown University), Alexander S. Kulikov (Steklov Institute of Mathematics at St. Petersburg), Ryan Williams (MIT)
Shrinkage of Decision Lists and DNF Formulas [video | slack]
Benjamin Rossman (Duke University)
Computation Over the Noisy Broadcast Channel with Malicious Parties [video | slack]
Klim Efremenko (Ben-Gurion University), Gillat Kol (Princeton University), Dmitry Paramonov (Princeton University), Raghuvansh R. Saxena (Princeton University)
Communication memento: Memoryless communication complexity [video | slack]
Srinivasan Arunachalam (IBM Research), Supartha Podder (University of Ottawa, Canada)
Differentially Oblivious Turing Machines [video | slack]
Ilan Komargodski (NTT Research and Hebrew University), Elaine Shi (Cornell University)

January 8th

Machine Learning
Room A
Chair: Sebastien Bubeck
Dynamic inference in probabilistic graphical models [video | slack]
Weiming Feng (Nanjing University), Kun He (Shenzhen University, SICS), Xiaoming Sun (ICT,CAS), Yitong Yin (Nanjing University)
Interactive Proofs for Verifying Machine Learning [video | slack]
Jonathan Shafer (UC Berkeley), Guy N. Rothblum (Weizmann Institute of Science), Shafi Goldwasser (UC Berkeley), Amir Yehudayoff (Technion-IIT)
Training (Overparametrized) Neural Networks in Near-Linear Time [video | slack]
Binghui Peng (Columbia University), Zhao Song (Princeton), Jan van den Brand (KTH Royal Institute of Technology), Omri Weinstein (Columbia University)
Counterexamples to the Low-Degree Conjecture [video | slack]
Justin Holmgren (NTT Research), Alexander S. Wein (Courant Institute, NYU)
Tight Hardness Results for Training Depth-2 ReLU Networks [video | slack]
Daniel Reichman (WPI), Pasin Manurangsi (Google Research), Subhi Goel (University of Texas at Austin), Adam R. Klivans (University of Texas at Austin)
Codes and information
Room B
Chair: Andris Ambainis
Towards local testability for quantum coding [video | slack]
Anthony Leverrier (Inria), Vivien Londe (Inria, Institut de Mathématiques de Bordeaux, Microsoft), Gilles Zémor (Institut de Mathématiques de Bordeaux)
Sharp Threshold Rates for Random Codes [video | slack]
Venkatesan Guruswami (CMU), Jonathan Mosheiff (CMU), Nicolas Resch (CWI), Shashwat Silas (Stanford), Mary Wootters (Stanford)
High-entropy dual functions and locally decodable codes [video | slack]
Farrokh Labib (CWI), Jop Briet (CWI)
Error Correcting Codes for Uncompressed Messages [video | slack]
Ofer Grossman (MIT), Justin Holmgren (NTT Research)
The entropy of lies: playing twenty questions with a liar [video | slack]
Yuval Dagan (MIT), Yuval Filmus (Technion), Daniel Kane (UCSD), Shay Moran (Technion)
Algorithimc Game Theory
Room A
Chair: Aviad Rubenstein
Delegated Stochastic Probing [video | slack]
Curtis Bechtel (University of Southern California), Shaddin Dughmi (University of Southern California)
Relaxing Common Belief for Social Networks [video | slack]
Noah Burrell (University of Michigan), Grant Schoenebeck (University of Michigan)
Approximately Strategyproof Tournament Rules in the Probabilistic Setting [video | slack]
Kimberly Ding (Princeton University), S. Matthew Weinberg (Princeton University)
Pipeline Interventions [video | slack]
Eshwar Ram Arunachaleswaran (University of Pennsylvania), Sampath Kannan (University of Pennsylvania), Aaron Roth (University of Pennsylvania), Juba Ziani (University of Pennsylvania)
Learning and Strongly Truthful Multi-task Setting Peer Prediction: A Variational Approach [video | slack]
Grant Schoenebeck (University of Michigan), Fang-Yi Yu (Harvard University)
Online and streaming algorithms
Room B
Chair: Sam Hopkins
Metrical Service Systems with Transformations [video | slack]
Sebastien Bubeck (Microsoft Research), Niv Buchbinder (Tel Aviv Univrsity), Christian Coester (CWI), Mark Sellke (Stanford University)
Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility [video | slack]
José Correa (Universidad de Chile), Paul Dütting (London School of Economics), Felix Fischer (Queen Mary University of London), Kevin Schewior (Universität zu Köln), Bruno Ziliotto (Université Paris-Dauphine)
Online Search With a Hint [video | slack]
Spyros Angelopoulos (CNRS and Sorbonne University)
Online Paging with a Vanishing Regret [video | slack]
Yuval Emek (Technion), Shay Kutten (Technion, Israel), Yangguang Shi (Technion)
Sensitivity Analysis of the Maximum Matching Problem [video | slack]
Yuichi Yoshida (National Institute of Informatics), Samson Zhou (Carnegie Mellon University)
12:30-13:30 Virtual coffee break in
Room A
Chair: Sebastien Bubeck
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration [video | slack]
Michael B. Cohen (MIT), Aaron Sidford (Stanford University), Kevin Tian (Stanford University)
Majorizing Measures for the Optimizer [video | slack]
Sander Borst (CWI Amsterdam), Daniel Dadush (CWI Amsterdam), Neil Olver (London School of Economics), Makrand Sinha (CWI Amsterdam)
Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation [video | slack]
Cameron Musco (University of Massachusetts Amherst), Christopher Musco (New York University), David P. Woodruff (Carnegie Mellon University)
Agnostic learning with unknown utilities [video | slack]
Kush Bhatia (University of California Berkeley), Peter L. Bartlett (University of California, Berkeley), Anca Dragan (University of California, Berkeley), Jacob Steinhardt (University of California, Berkeley)
No quantum speedup over gradient descent for non-smooth convex optimization [video | slack]
Ankit Garg (Microsoft Research), Robin Kothari (Microsoft Quantum), Praneeth Netrapalli (Microsoft Research), Suhail Sherif (School of Technology and Computer Science, TIFR, Mumbai)
Algebraic and circuit complexity
Room B
Chair: Anindya De
Complexity measures on symmetric group and beyond [video | slack]
Neta Dafni (Technion), Yuval Filmus (Technion), Noam Lifshitz (Hebrew University), Nathan Lindzey (CU Boulder), Marc Vinyals (Technion)
On the Complexity of #CSP^d [video | slack]
Jiabao Lin (Shanghai University of Finance and Economics)
On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism-completeness [video | slack]
Joshua A. Grochow (University of Colorado, Boulder), Youming Qiao (University of Technology Sydney)
A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits [video | slack]
Mrinal Kumar (IIT Bombay), Ben Lee Volk (Caltech/UT Austin)
A Largish Sum-of-Squares Implies Circuit Hardness and Derandomization [video | slack]
Pranjal Dutta (Chennai Mathematical Institute), Nitin Saxena (IIT Kanpur), Thomas Thierauf (Aalen University)