| 2022 | An improved approximation algorithm for the minimum | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang |
| 2022 | Subquadratic dynamic path reporting in directed graphs against an adaptive adversary. | Adam Karczmarz, Anish Mukherjee, Piotr Sankowski |
| 2022 | Combinatorics via closed orbits: number theoretic Ramanujan graphs are not unique neighbor expanders. | Amitay Kamber, Tali Kaufman |
| 2022 | Tight dynamic problem lower bounds from generalized BMM and OMv. | Ce Jin, Yinzhan Xu |
| 2022 | Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion. | Bart M. P. Jansen, Michal Wlodarczyk |
| 2022 | Improved iteration complexities for overconstrained | Arun Jambulapati, Yang P. Liu, Aaron Sidford |
| 2022 | Approximate counting and sampling via local central limit theorems. | Vishesh Jain, Will Perkins, Ashwin Sah, Mehtaab Sawhney |
| 2022 | List-decodable covariance estimation. | Misha Ivkov, Pravesh K. Kothari |
| 2022 | Reproducibility in learning. | Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell |
| 2022 | Robustness of average-case meta-complexity via pseudorandomness. | Rahul Ilango, Hanlin Ren, Rahul Santhanam |
| 2022 | Byzantine agreement in polynomial time with near-optimal resilience. | Shang-En Huang, Seth Pettie, Leqi Zhu |
| 2022 | Matrix discrepancy from Quantum communication. | Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty |
| 2022 | Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism. | Samuel B. Hopkins, Gautam Kamath, Mahbod Majid |
| 2022 | A strong version of Cobham's theorem. | Philipp Hieronymi, Christian Schulz |
| 2022 | Verifying the unseen: interactive proofs for label-invariant distribution properties. | Tal Herman, Guy N. Rothblum |
| 2022 | Breaking the | Zhiyang He, Jason Li |
| 2022 | Optimizing strongly interacting fermionic Hamiltonians. | Matthew B. Hastings, Ryan O'Donnell |
| 2022 | Randomized communication and implicit graph representations. | Nathaniel Harms, Sebastian Wild, Viktor Zamaraev |
| 2022 | Near-optimal distributed degree+1 coloring. | Magns M. Halldrsson, Fabian Kuhn, Alexandre Nolin, Tigran Tonoyan |
| 2022 | Improved communication complexity of fault-tolerant consensus. | Mohammad Taghi Hajiaghayi, Dariusz R. Kowalski, Jan Olkowski |
| 2022 | On the complexity of two-party differential privacy. | Iftach Haitner, Noam Mazor, Jad Silbak, Eliad Tsfadia |
| 2022 | Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality. | Bernhard Haeupler, Harald Rcke, Mohsen Ghaffari |
| 2022 | Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. | Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar |
| 2022 | Hypercontractivity on high dimensional expanders. | Tom Gur, Noam Lifshitz, Siqi Liu |
| 2022 | The optimal error resilience of interactive communication over binary channels. | Meghal Gupta, Rachel Yun Zhang |