| 2021 | Hop-constrained oblivious routing. | Mohsen Ghaffari, Bernhard Haeupler, Goran Zuzic |
| 2021 | Indistinguishability obfuscation from circular security. | Romain Gay, Rafael Pass |
| 2021 | Fully dynamic approximation of LIS in polylogarithmic time. | Pawel Gawrychowski, Wojciech Janczewski |
| 2021 | Finding large induced sparse subgraphs in | Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski |
| 2021 | Approximating Nash social welfare under rado valuations. | Jugal Garg, Edin Husic, Lszl A. Vgh |
| 2021 | Clan embeddings into trees, and low treewidth graphs. | Arnold Filtser, Hung Le |
| 2021 | Revelation gap for pricing from samples. | Yiding Feng, Jason D. Hartline, Yingkai Li |
| 2021 | Sampling constraint satisfaction solutions in the local lemma regime. | Weiming Feng, Kun He, Yitong Yin |
| 2021 | Eliminating intermediate measurements in space-bounded Quantum computation. | Bill Fefferman, Zachary Remscrim |
| 2021 | The complexity of gradient descent: CLS = PPAD ∩ PLS. | John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani |
| 2021 | Optimal error resilience of adaptive message exchange. | Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena |
| 2021 | Outcome indistinguishability. | Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona |
| 2021 | Efficient two-sided markets with limited information. | Paul Dtting, Federico Fusco, Philip Lazos, Stefano Leonardi, Rebecca Reiffenhuser |
| 2021 | Distributed weighted min-cut in nearly-optimal time. | Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai |
| 2021 | A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path. | Sally Dong, Yin Tat Lee, Guanghao Ye |
| 2021 | The communication complexity of payment computation. | Shahar Dobzinski, Shiri Ron |
| 2021 | Efficiently learning halfspaces with Tsybakov noise. | Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis |
| 2021 | Optimal testing of discrete distributions with high probability. | Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, Eric Price |
| 2021 | The communication complexity of multiparty set disjointness under product distributions. | Nachum Dershowitz, Rotem Oshman, Tal Roth |
| 2021 | Robust testing of low dimensional functions. | Anindya De, Elchanan Mossel, Joe Neeman |
| 2021 | The complexity of constrained min-max optimization. | Constantinos Daskalakis, Stratis Skoulakis, Manolis Zampetakis |
| 2021 | Sample-optimal and efficient learning of tree Ising models. | Constantinos Daskalakis, Qinxuan Pan |
| 2021 | Tight conditional lower bounds for approximating diameter in directed graphs. | Mina Dalirrooyfard, Nicole Wein |
| 2021 | Learning Ising models from one or multiple samples. | Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Anthimos Vardis Kandiros |
| 2021 | A full complexity dichotomy for immanant families. | Radu Curticapean |