| 2020 | Computations with greater quantum depth are strictly more powerful (relative to an oracle). | Matthew Coudron, Sanketh Menda |
| 2020 | Catalytic approaches to the tree evaluation problem. | James Cook, Ian Mertz |
| 2020 | Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. | Nai-Hui Chia, Andrs Gilyn, Tongyang Li, Han-Hsuan Lin, Ewin Tang, Chunhao Wang |
| 2020 | On the need for large quantum depth. | Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai |
| 2020 | Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond. | Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, Nilesh Tripuraneni |
| 2020 | Strong average-case lower bounds from non-trivial derandomization. | Lijie Chen, Hanlin Ren |
| 2020 | Sharp threshold results for computational complexity. | Lijie Chen, Ce Jin, R. Ryan Williams |
| 2020 | Smoothed complexity of local max-cut and binary max-CSP. | Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang |
| 2020 | Learning mixtures of linear regressions in subexponential time via Fourier moments. | Sitan Chen, Jerry Li, Zhao Song |
| 2020 | Efficiently learning structured distributions from untrusted batches. | Sitan Chen, Jerry Li, Ankur Moitra |
| 2020 | Constant girth approximation for directed graphs in subquadratic time. | Shiri Chechik, Yang P. Liu, Omer Rotem, Aaron Sidford |
| 2020 | Distance sensitivity oracles with subcubic preprocessing time and fast query time. | Shiri Chechik, Sarel Cohen |
| 2020 | XOR lemmas for resilient functions against polynomials. | Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman |
| 2020 | Extractors for adversarial sources via extremal hypergraphs. | Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li |
| 2020 | Approximating text-to-pattern Hamming distances. | Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat |
| 2020 | Efficient construction of directed hopsets and parallel approximate shortest paths. | Nairen Cao, Jeremy T. Fineman, Katina Russell |
| 2020 | Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. | Jaroslaw Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli |
| 2020 | Top-k-convolution and the quest for near-linear output-sensitive subset sum. | Karl Bringmann, Vasileios Nakos |
| 2020 | Solving tall dense linear programs in nearly linear time. | Jan van den Brand, Yin Tat Lee, Aaron Sidford, Zhao Song |
| 2020 | Constant-factor approximation of near-linear edit distance in near-linear time. | Joshua Brakensiek, Aviad Rubinstein |
| 2020 | Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures. | Christian Borgs, Jennifer T. Chayes, Tyler Helmuth, Will Perkins, Prasad Tetali |
| 2020 | Post-quantum zero knowledge in constant rounds. | Nir Bitansky, Omri Shmueli |
| 2020 | Unbounded lower bound for k-server against weak adversaries. | Marcin Bienkowski, Jaroslaw Byrka, Christian Coester, Lukasz Jez |
| 2020 | Improved bounds for perfect sampling of k-colorings in graphs. | Siddharth Bhandari, Sayantan Chakraborty |
| 2020 | Optimal time and space leader election in population protocols. | Petra Berenbrink, George Giakkoupis, Peter Kling |