| 2021 | 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, Virtual Conference, January 6-8, 2021 James R. Lee |
| 2021 | A Generalized Matching Reconfiguration Problem. Noam Solomon, Shay Solomon |
| 2021 | A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization. Pranjal Dutta, Nitin Saxena, Thomas Thierauf |
| 2021 | A Model for Ant Trail Formation and its Convergence Properties (Extended Abstract). Moses Charikar, Shivam Garg, Deborah M. Gordon, Kirankumar Shiragur |
| 2021 | A New Connection Between Node and Edge Depth Robust Graphs. Jeremiah Blocki, Mike Cinkoske |
| 2021 | A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits. Mrinal Kumar, Ben Lee Volk |
| 2021 | Agnostic Learning with Unknown Utilities. Kush Bhatia, Peter L. Bartlett, Anca D. Dragan, Jacob Steinhardt |
| 2021 | Algorithmic Persuasion with Evidence. Martin Hoefer, Pasin Manurangsi, Alexandros Psomas |
| 2021 | Algorithms and Hardness for Multidimensional Range Updates and Queries. Joshua Lau, Angus Ritossa |
| 2021 | An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability. Rajko Nenadov, Angelika Steger, Pascal Su |
| 2021 | Approximately Strategyproof Tournament Rules in the Probabilistic Setting. Kimberly Ding, S. Matthew Weinberg |
| 2021 | Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract). Yiding Feng, Rad Niazadeh |
| 2021 | Black-Box Uselessness: Composing Separations in Cryptography. Geoffroy Couteau, Pooya Farshim, Mohammad Mahmoody |
| 2021 | Block Rigidity: Strong Multiplayer Parallel Repetition Implies Super-Linear Lower Bounds for Turing Machines. Kunal Mittal, Ran Raz |
| 2021 | Bounds on the QAC^0 Complexity of Approximating Parity. Gregory Rosenthal |
| 2021 | Buying Data over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions. Nicole Immorlica, Ian A. Kash, Brendan Lucier |
| 2021 | Circuit Depth Reductions. Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams |
| 2021 | Circular Trace Reconstruction. Shyam Narayanan, Michael Ren |
| 2021 | Communication Memento: Memoryless Communication Complexity. Srinivasan Arunachalam, Supartha Podder |
| 2021 | Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?). Russell Impagliazzo, Sam McGuire |
| 2021 | Comparison Graphs: A Unified Method for Uniformity Testing. Uri Meir |
| 2021 | Complete Problems for Multi-Pseudodeterministic Computations. Peter Dixon, A. Pavan, N. V. Vinodchandran |
| 2021 | Complexity Measures on the Symmetric Group and Beyond (Extended Abstract). Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, Marc Vinyals |
| 2021 | Computation over the Noisy Broadcast Channel with Malicious Parties. Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena |
| 2021 | Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets. Vijay V. Vazirani, Mihalis Yannakakis |
| 2021 | Counterexamples to the Low-Degree Conjecture. Justin Holmgren, Alexander S. Wein |
| 2021 | Delegated Stochastic Probing. Curtis Bechtel, Shaddin Dughmi |
| 2021 | Differentially Oblivious Turing Machines. Ilan Komargodski, Elaine Shi |
| 2021 | Distributed Load Balancing: A New Framework and Improved Guarantees. Sara Ahmadian, Allen Liu, Binghui Peng, Morteza Zadimoghaddam |
| 2021 | Distributed Quantum Proofs for Replicated Data. Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz |
| 2021 | Dynamic Inference in Probabilistic Graphical Models. Weiming Feng, Kun He, Xiaoming Sun, Yitong Yin |
| 2021 | Erasure-Resilient Sublinear-Time Graph Algorithms. Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma |
| 2021 | Error Correcting Codes for Uncompressed Messages. Ofer Grossman, Justin Holmgren |
| 2021 | Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming! Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra, Anannya Upasana |
| 2021 | Explicit SoS Lower Bounds from High-Dimensional Expanders. Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani |
| 2021 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2021 | High-Entropy Dual Functions and Locally Decodable Codes (Extended Abstract). Jop Briët, Farrokh Labib |
| 2021 | How to Sell Information Optimally: An Algorithmic Study. Yang Cai, Grigoris Velegkas |
| 2021 | Interactive Proofs for Verifying Machine Learning. Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, Amir Yehudayoff |
| 2021 | Is the Space Complexity of Planted Clique Recovery the Same as That of Detection? Jay Mardia |
| 2021 | Learning and Strongly Truthful Multi-Task Peer Prediction: A Variational Approach. Grant Schoenebeck, Fang-Yi Yu |
| 2021 | Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma. Stefan Dziembowski, Grzegorz Fabianski, Sebastian Faust, Siavash Riahi |
| 2021 | Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines. Zachary Remscrim |
| 2021 | Majorizing Measures for the Optimizer. Sander Borst, Daniel Dadush, Neil Olver, Makrand Sinha |
| 2021 | Metrical Service Systems with Transformations. Sébastien Bubeck, Niv Buchbinder, Christian Coester, Mark Sellke |
| 2021 | No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization. Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif |
| 2021 | Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract). Moshe Babaioff, Richard Cole, Jason D. Hartline, Nicole Immorlica, Brendan Lucier |
| 2021 | On Basing Auxiliary-Input Cryptography on NP-Hardness via Nonadaptive Black-Box Reductions. Mikito Nanashima |
| 2021 | On Distributed Differential Privacy and Counting Distinct Elements. Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi |
| 2021 | On Rich 2-to-1 Games. Mark Braverman, Subhash Khot, Dor Minzer |
| 2021 | On the Complexity of #CSP^d. Jiabao Lin |
| 2021 | On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. Joshua A. Grochow, Youming Qiao |
| 2021 | Online Paging with a Vanishing Regret. Yuval Emek, Shay Kutten, Yangguang Shi |
| 2021 | Online Search with a Hint. Spyros Angelopoulos |
| 2021 | Ordered Graph Limits and Their Applications. Omri Ben-Eliezer, Eldar Fischer, Amit Levi, Yuichi Yoshida |
| 2021 | Pipeline Interventions. Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth, Juba Ziani |
| 2021 | Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime. Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha |
| 2021 | Pseudobinomiality of the Sticky Random Walk. Venkatesan Guruswami, Vinayak M. Kumar |
| 2021 | Pseudorandom Generators for Unbounded-Width Permutation Branching Programs. William M. Hoza, Edward Pyne, Salil P. Vadhan |
| 2021 | Quantitative Correlation Inequalities via Semigroup Interpolation. Anindya De, Shivam Nadimpalli, Rocco A. Servedio |
| 2021 | Quantum Versus Randomized Communication Complexity, with Efficient Players. Uma Girish, Ran Raz, Avishay Tal |
| 2021 | Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists). Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma |
| 2021 | Randomness and Fairness in Two-Sided Matching with Limited Interviews. Hedyeh Beyhaghi, Éva Tardos |
| 2021 | Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration. Michael B. Cohen, Aaron Sidford, Kevin Tian |
| 2021 | Relaxing Common Belief for Social Networks. Noah Burrell, Grant Schoenebeck |
| 2021 | Robust Quantum Entanglement at (Nearly) Room Temperature. Lior Eldar |
| 2021 | Sample Efficient Identity Testing and Independence Testing of Quantum States. Nengkun Yu |
| 2021 | Sampling Arborescences in Parallel. Nima Anari, Nathan Hu, Amin Saberi, Aaron Schild |
| 2021 | Self-Testing of a Single Quantum Device Under Computational Assumptions. Tony Metger, Thomas Vidick |
| 2021 | Sensitivity Analysis of the Maximum Matching Problem. Yuichi Yoshida, Samson Zhou |
| 2021 | Sequential Defaulting in Financial Networks. Pál András Papp, Roger Wattenhofer |
| 2021 | Sharp Threshold Rates for Random Codes. Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters |
| 2021 | Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract). Yuval Filmus, Or Meir, Avishay Tal |
| 2021 | Shrinkage of Decision Lists and DNF Formulas. Benjamin Rossman |
| 2021 | Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation. Cameron Musco, Christopher Musco, David P. Woodruff |
| 2021 | Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits. Boaz Barak, Chi-Ning Chou, Xun Gao |
| 2021 | The Complexity of Finding Fair Independent Sets in Cycles. Ishay Haviv |
| 2021 | The Entropy of Lies: Playing Twenty Questions with a Liar. Yuval Dagan, Yuval Filmus, Daniel Kane, Shay Moran |
| 2021 | The Quantum Supremacy Tsirelson Inequality. William Kretschmer |
| 2021 | The Strongish Planted Clique Hypothesis and Its Consequences. Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm |
| 2021 | The Variable-Processor Cup Game. William Kuszmaul, Alek Westover |
| 2021 | Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality. Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra |
| 2021 | Tiered Random Matching Markets: Rank Is Proportional to Popularity. Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, Geng Zhao |
| 2021 | Tight Hardness Results for Training Depth-2 ReLU Networks. Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, Daniel Reichman |
| 2021 | Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers. Abhijit Mudigonda, R. Ryan Williams |
| 2021 | Total Functions in the Polynomial Hierarchy. Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, Christos H. Papadimitriou |
| 2021 | Towards Local Testability for Quantum Coding. Anthony Leverrier, Vivien Londe, Gilles Zémor |
| 2021 | Training (Overparametrized) Neural Networks in Near-Linear Time. Jan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein |
| 2021 | Two Combinatorial MA-Complete Problems. Dorit Aharonov, Alex B. Grilo |
| 2021 | Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution. Olaf Beyersdorff, Benjamin Böhm |
| 2021 | Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility (Extended Abstract). José Correa, Paul Dütting, Felix A. Fischer, Kevin Schewior, Bruno Ziliotto |