| 2021 | A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings. | Dorna Abdolazimi, Kuikui Liu, Shayan Oveis Gharan |
| 2021 | APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. | Amir Abboud, Robert Krauthgamer, Ohad Trabelsi |
| 2021 | Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron. | Emmanuel Abbe, Shuangping Li, Allan Sly |
| 2021 | A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs. | Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak |
| 2021 | Random walks and forbidden minors III: $\text{poly}\left(d\varepsilon ^{-1}\right)$-time partition oracles for minor-free graph classes. | Akash Kumar, C. Seshadhri, Andrew Stolman |
| 2021 | Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies. | Marco Bressan, Marc Roth |
| 2021 | Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. | Oded Goldreich, Avi Wigderson |
| 2021 | Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise. | Lijie Chen, Roei Tell |
| 2021 | Fully Dynamic s-t Edge Connectivity in Subpolynomial Time (Extended Abstract). | Wenyu Jin, Xiaorui Sun |
| 2021 | Random Order Online Set Cover is as Easy as Offline. | Anupam Gupta, Gregory Kehne, Roie Levin |
| 2021 | On the Nisan-Ronen conjecture. | George Christodoulou, Elias Koutsoupias, Annamria Kovcs |
| 2021 | A direct product theorem for quantum communication complexity with applications to device-independent QKD. | Rahul Jain, Srijita Kundu |
| 2021 | Constructive Separations and Their Consequences. | Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams |
| 2021 | A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows. | Anupam Gupta, Amit Kumar, Debmalya Panigrahi |
| 2020 | Monochromatic Triangles, Triangle Listing and APSP. | Virginia Vassilevska Williams, Yinzhan Xu |
| 2020 | Testing linear-invariant properties. | Jonathan Tidor, Yufei Zhao |
| 2020 | Towards Optimal Separations between Quantum and Randomized Query Complexities. | Avishay Tal |
| 2020 | Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise. | Noah Shutty, Mary Wootters, Patrick Hayden |
| 2020 | Lazy Search Trees. | Bryce Sandlund, Sebastian Wild |
| 2020 | Counting Small Induced Subgraphs Satisfying Monotone Properties. | Marc Roth, Johannes Schmitt, Philip Wellnitz |
| 2020 | Local Proofs Approaching the Witness Length [Extended Abstract]. | Noga Ron-Zewi, Ron D. Rothblum |
| 2020 | Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. | Susanna F. de Rezende, Or Meir, Jakob Nordstrm, Toniann Pitassi, Robert Robere, Marc Vinyals |
| 2020 | KRW Composition Theorems via Lifting. | Susanna F. de Rezende, Or Meir, Jakob Nordstrm, Toniann Pitassi, Robert Robere |
| 2020 | Is it Easier to Prove Theorems that are Guaranteed to be True? | Rafael Pass, Muthuramakrishnan Venkitasubramaniam |
| 2020 | Explicit near-fully X-Ramanujan graphs. | Ryan O'Donnell, Xinyu Wu |