| 2020 | Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes. | Zvika Brakerski, Yael Tauman Kalai, Raghuvansh R. Saxena |
| 2020 | Coded trace reconstruction in a constant number of traces. | Joshua Brakensiek, Ray Li, Bruce Spang |
| 2020 | Correlated Pseudorandom Functions from Variable-Density LPN. | Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Scholl |
| 2020 | Smoothed Complexity of 2-player Nash Equilibria. | Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein |
| 2020 | Twin-width I: tractable FO model checking. | douard Bonnet, Eun Jung Kim, Stphan Thomass, Rmi Watrigant |
| 2020 | Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs. | Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal |
| 2020 | Near-Optimal Decremental SSSP in Dense Weighted Digraphs. | Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen |
| 2020 | Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing. | Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak |
| 2020 | Proximity Gaps for Reed-Solomon Codes. | Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf |
| 2020 | Symmetries, Graph Properties, and Quantum Speedups. | Shalev Ben-David, Andrew M. Childs, Andrs Gilyn, William Kretschmer, Supartha Podder, Daochen Wang |
| 2020 | A New Minimax Theorem for Randomized Algorithms (Extended Abstract). | Shalev Ben-David, Eric Blais |
| 2020 | A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract. | Shalev Ben-David, Eric Blais |
| 2020 | Stochastic Weighted Matching: (Stochastic Weighted Matching: (1-ε) Approximation -\varepsilon$) Approximation. | Soheil Behnezhad, Mahsa Derakhshan |
| 2020 | Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time. | Jess Banks, Jorge Garza-Vargas, Archit Kulkarni, Nikhil Srivastava |
| 2020 | Distributed Lower Bounds for Ruling Sets. | Alkida Balliu, Sebastian Brandt, Dennis Olivetti |
| 2020 | Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures. | Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, Pravesh K. Kothari |
| 2020 | Robust and Sample Optimal Algorithms for PSD Low Rank Approximation. | Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff |
| 2020 | Testing Positive Semi-Definiteness via Random Submatrices. | Ainesh Bakshi, Nadiia Chepurko, Rajesh Jayaram |
| 2020 | Communication complexity of Nash equilibrium in potential games (extended abstract). | Yakov Babichenko, Aviad Rubinstein |
| 2020 | Beyond Tree Embeddings - a Deterministic Framework for Network Design with Deadlines or Delay. | Yossi Azar, Noam Touitou |
| 2020 | Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs. | Kyriakos Axiotis, Aleksander Madry, Adrian Vladu |
| 2020 | Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms. | Sepehr Assadi, Ran Raz |
| 2020 | Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. | Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu |
| 2020 | The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency. | Benny Applebaum, Eliran Kachlon, Arpita Patra |
| 2020 | Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving. | Simon Apers, Ronald de Wolf |