| 2021 | PPSZ is better than you think. | Dominik Scheder |
| 2021 | Almost Optimal Inapproximability of Multidimensional Packing Problems. | Sai Sandeep |
| 2021 | Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms. | Robert Robere, Jeroen Zuiddam |
| 2021 | Tradeoffs for small-depth Frege proofs. | Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan |
| 2021 | At most 3.55 | Cory Palmer, Dmtr Plvlgyi |
| 2021 | Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time. | Neil Olver, Leon Sering, Laura Vargas Koch |
| 2021 | One-step replica symmetry breaking of random regular NAE-SAT. | Danny Nam, Allan Sly, Youngtak Sohn |
| 2021 | New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems. | Guillaume Moroz |
| 2021 | Approximating Maximum Independent Set for Rectangles in the Plane. | Joseph S. B. Mitchell |
| 2021 | On Classifying Continuous Constraint Satisfaction problems. | Tillmann Miltzow, Reinier F. Schmiermann |
| 2021 | Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance. | Xiao Mao |
| 2021 | Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning. | Yuanzhi Li, Ruosong Wang, Lin F. Yang |
| 2021 | A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations. | Wenzheng Li, Jan Vondrk |
| 2021 | On statistical inference when fixed points of belief propagation are unstable. | Siqi Liu, Sidhanth Mohanty, Prasad Raghavendra |
| 2021 | Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. | Nutan Limaye, Srikanth Srinivasan, Sbastien Tavenas |
| 2021 | Optimal Approximate Distance Oracle for Planar Graphs. | Hung Le, Christian Wulff-Nilsen |
| 2021 | The Reachability Problem for Petri Nets is Not Primitive Recursive. | Jrme Leroux |
| 2021 | Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$. | Jasper C. H. Lee, Paul Valiant |
| 2021 | Sharper bounds on the Fourier concentration of DNFs. | Victor Lecomte, Li-Yang Tan |
| 2021 | Stochastic and Worst-Case Generalized Sorting Revisited. | William Kuszmaul, Shyam Narayanan |
| 2021 | The Hardest Explicit Construction. | Oliver Korten |
| 2021 | A Single-Exponential Time 2-Approximation Algorithm for Treewidth. | Tuukka Korhonen |
| 2021 | Quantum supremacy and hardness of estimating output probabilities of quantum circuits. | Yasuhiro Kondo, Ryuhei Mori, Ramis Movassagh |
| 2021 | Small-space and streaming pattern matching with $k$ edits. | Tomasz Kociumaka, Ely Porat, Tatiana Starikovskaya |
| 2021 | A Gap-ETH-Tight Approximation Scheme for Euclidean TSP. | Sndor Kisfaludi-Bak, Jesper Nederlof, Karol Wegrzycki |