| 2020 | A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. | Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak |
| 2020 | Tight Quantum Time-Space Tradeoffs for Function Inversion. | Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian |
| 2020 | Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat. | Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy |
| 2020 | List Decodable Mean Estimation in Nearly Linear Time. | Yeshwanth Cherapanamjeri, Sidhanth Mohanty, Morris Yau |
| 2020 | Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time. | Mahdi Cheraghchi, Vasileios Nakos |
| 2020 | On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract. | Lijie Chen, Ron D. Rothblum, Roei Tell, Eylon Yogev |
| 2020 | Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. | Zongchen Chen, Kuikui Liu, Eric Vigoda |
| 2020 | Near-linear Size Hypergraph Cut Sparsifiers. | Yu Chen, Sanjeev Khanna, Ansh Nagda |
| 2020 | Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers. | Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, Thatchaphol Saranurak |
| 2020 | Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. | Lijie Chen, Xin Lyu, R. Ryan Williams |
| 2020 | Extractors and Secret Sharing Against Bounded Collusion Protocols. | Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, David Zuckerman |
| 2020 | On the Existence of Algebraically Natural Proofs. | Prerona Chatterjee, Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, Anamay Tengse |
| 2020 | Kernel Density Estimation through Density Constrained Near Neighbor Search. | Moses Charikar, Michael Kapralov, Navid Nouri, Paris Siminelakis |
| 2020 | Faster Approximate Pattern Matching: A Unified Approach. | Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz |
| 2020 | Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization. | Yi-Jun Chang, Thatchaphol Saranurak |
| 2020 | Hypergraph $k$-cut for fixed $k$ in deterministic polynomial time. | Karthekeyan Chandrasekaran, Chandra Chekuri |
| 2020 | Coordinate Methods for Matrix Games. | Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian |
| 2020 | Mechanisms for a No-Regret Agent: Beyond the Common Prior. | Modibo K. Camara, Jason D. Hartline, Aleck C. Johnsen |
| 2020 | Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs. | Jin-Yi Cai, Artem Govorov |
| 2020 | An Equivalence Between Private Classification and Online Prediction. | Mark Bun, Roi Livni, Shay Moran |
| 2020 | Entanglement is Necessary for Optimal Quantum Property Testing. | Sbastien Bubeck, Sitan Chen, Jerry Li |
| 2020 | QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge. | Anne Broadbent, Alex B. Grilo |
| 2020 | The Coin Problem with Applications to Data Streams. | Mark Braverman, Sumegha Garg, David P. Woodruff |
| 2020 | Near Optimal Linear Algebra in the Online and Sliding Window Models. | Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou |
| 2020 | Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. | Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang |