| 2020 | LDPC Codes Achieve List Decoding Capacity. | Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters |
| 2020 | Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. | Laura Mancinska, David E. Roberson |
| 2020 | Symbolic determinant identity testing (SDIT) is not a null cone problem; and the symmetries of algebraic varieties. | Visu Makam, Avi Wigderson |
| 2020 | Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay. | Biswaroop Maiti, Rajmohan Rajaraman, David Stalfa, Zoya Svitkina, Aravindan Vijayaraghavan |
| 2020 | Maximizing Determinants under Matroid Constraints. | Vivek Madan, Aleksandar Nikolov, Mohit Singh, Uthaipon Tantipongpipat |
| 2020 | A Parameterized Approximation Scheme for Min $k$-Cut. | Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan |
| 2020 | On One-way Functions and Kolmogorov Complexity. | Yanyi Liu, Rafael Pass |
| 2020 | Deterministic Min-cut in Poly-logarithmic Max-flows. | Jason Li, Debmalya Panigrahi |
| 2020 | Tree-depth and the Formula Complexity of Subgraph Isomorphism. | Deepanshu Kush, Benjamin Rossman |
| 2020 | An Adaptive Step Toward the Multiphase Conjecture. | Young Kun-Ko, Omri Weinstein |
| 2020 | Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations. | Ariel Kulik, Hadas Shachnai |
| 2020 | Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance. | Tomasz Kociumaka, Barna Saha |
| 2020 | Resolution of the Burrows-Wheeler Transform Conjecture. | Dominik Kempa, Tomasz Kociumaka |
| 2020 | Towards a Proof of the Fourier-Entropy Conjecture? | Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, Muli Safra |
| 2020 | Unit Capacity Maxflow in Almost $O(m^{4/3})$ Time. | Tarun Kathuria, Yang P. Liu, Aaron Sidford |
| 2020 | Collaborative Top Distribution Identifications with Limited Interaction (Extended Abstract). | Nikolai Karpov, Qin Zhang, Yuan Zhou |
| 2020 | A Faster Interior Point Method for Semidefinite Programming. | Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, Zhao Song |
| 2020 | Unique Decoding of Explicit $\varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound. | Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani |
| 2020 | Constant Depth Formula and Partial Function Versions of MCSP are Hard. | Rahul Ilango |
| 2020 | Approximation Algorithms for Stochastic Minimum-Norm Combinatorial Optimization. | Sharat Ibrahimpur, Chaitanya Swamy |
| 2020 | Subexponential LPs Approximate Max-Cut. | Samuel B. Hopkins, Tselil Schramm, Luca Trevisan |
| 2020 | Point Location and Active Learning: Learning Halfspaces Almost Optimally. | Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan |
| 2020 | Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity. | Shuichi Hirahara |
| 2020 | Optimal anytime regret for two experts. | Nicholas J. A. Harvey, Christopher Liaw, Edwin A. Perkins, Sikander Randhawa |
| 2020 | Benchmark Design and Prior-independent Optimization. | Jason D. Hartline, Aleck C. Johnsen, Yingkai Li |