| 2020 | Contention resolution without collision detection. | Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie |
| 2020 | Stochastic matching with few queries: (1-ε) approximation. | Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi |
| 2020 | Online vector balancing and geometric discrepancy. | Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha |
| 2020 | A lower bound for parallel submodular minimization. | Eric Balkanski, Yaron Singer |
| 2020 | Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits. | Sepehr Assadi, Chen Wang |
| 2020 | Separating the communication complexity of truthful and non-truthful combinatorial auctions. | Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg |
| 2020 | Better secret sharing via robust conditional disclosure of secrets. | Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter |
| 2020 | Entanglement subvolume law for 2d frustration-free spin systems. | Anurag Anshu, Itai Arad, David Gosset |
| 2020 | Parallel approximate undirected shortest paths via low hop emulators. | Alexandr Andoni, Clifford Stein, Peilin Zhong |
| 2020 | One-shot signatures and applications to hybrid quantum/classical authentication. | Ryan Amos, Marios Georgiou, Aggelos Kiayias, Mark Zhandry |
| 2020 | Quadratic speedup for finding marked vertices by quantum walks. | Andris Ambainis, Andrs Gilyn, Stacey Jeffery, Martins Kokainis |
| 2020 | Improved bounds for the sunflower lemma. | Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang |
| 2020 | Improved analysis of higher order random walks and applications. | Vedat Levi Alev, Lap Chi Lau |
| 2020 | Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative? | Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret |
| 2020 | New hardness results for planar graph problems in p and an algorithm for sparsest cut. | Amir Abboud, Vincent Cohen-Addad, Philip N. Klein |
| 2020 | Fast hashing with strong concentration bounds. | Anders Aamand, Jakob Bk Tejs Knudsen, Mathias Bk Tejs Knudsen, Peter Michael Reichstein Rasmussen, Mikkel Thorup |
| 2020 | (Semi)Algebraic proofs over ±1 variables. | Dmitry Sokolov |
| 2020 | Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue. | Zhiyi Huang, Qiankun Zhang |
| 2020 | Estimating normalizing constants for log-concave distributions: algorithms and lower bounds. | Rong Ge, Holden Lee, Jianfeng Lu |
| 2020 | On the Nisan-Ronen conjecture for submodular valuations. | George Christodoulou, Elias Koutsoupias, Annamria Kovcs |
| 2020 | All non-trivial variants of 3-LDT are equivalent. | Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya |
| 2020 | Testing noisy linear functions for sparsity. | Xue Chen, Anindya De, Rocco A. Servedio |
| 2020 | A robust version of Hegedus's lemma, with applications. | Srikanth Srinivasan |
| 2019 | Optimal succinct rank data structure via approximate nonnegative tensor decomposition. | Huacheng Yu |
| 2019 | Separating monotone VP and VNP. | Amir Yehudayoff |