| 2016 | Bipartite perfect matching is in quasi-NC. | Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf |
| 2016 | The price of anarchy in large games. | Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, Vasilis Syrgkanis |
| 2016 | Bounded degree cosystolic expanders of every dimension. | Shai Evra, Tali Kaufman |
| 2016 | Routing under balance. | Alina Ene, Gary L. Miller, Jakub Pachocki, Aaron Sidford |
| 2016 | Online matching: haste makes waste! | Yuval Emek, Shay Kutten, Roger Wattenhofer |
| 2016 | Deterministic and probabilistic binary search in graphs. | Ehsan Emamjomeh-Zadeh, David Kempe, Vikrant Singhal |
| 2016 | Algorithmic Bayesian persuasion. | Shaddin Dughmi, Haifeng Xu |
| 2016 | Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders. | Shahar Dobzinski |
| 2016 | The fourier transform of poisson multinomial distributions and its algorithmic applications. | Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart |
| 2016 | The sample complexity of auctions with side information. | Nikhil R. Devanur, Zhiyi Huang, Christos-Alexandros Psomas |
| 2016 | On the effect of randomness on planted 3-coloring models. | Roee David, Uriel Feige |
| 2016 | A size-free CLT for poisson multinomials and its applications. | Constantinos Daskalakis, Anindya De, Gautam Kamath, Christos Tzamos |
| 2016 | A cost function for similarity-based hierarchical clustering. | Sanjoy Dasgupta |
| 2016 | Complexity theoretic limitations on learning halfspaces. | Amit Daniely |
| 2016 | Relating two property testing models for bounded degree directed graphs. | Artur Czumaj, Pan Peng, Christian Sohler |
| 2016 | Geometric median in nearly linear time. | Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, Aaron Sidford |
| 2016 | Watermarking cryptographic capabilities. | Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, Daniel Wichs |
| 2016 | Two-source dispersers for polylogarithmic entropy and improved ramsey graphs. | Gil Cohen |
| 2016 | Approximating connectivity domination in weighted bounded-genus graphs. | Vincent Cohen-Addad, ric Colin de Verdire, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld |
| 2016 | Improved approximation for node-disjoint paths in planar graphs. | Julia Chuzhoy, David H. K. Kim, Shi Li |
| 2016 | Near-optimal small-depth lower bounds for small distance connectivity. | Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan |
| 2016 | Basis collapse for holographic algorithms over all domain sizes. | Sitan Chen |
| 2016 | Explicit two-source extractors and resilient functions. | Eshan Chattopadhyay, David Zuckerman |
| 2016 | Extractors for sumset sources. | Eshan Chattopadhyay, Xin Li |
| 2016 | Non-malleable extractors and codes, with their many tampered extensions. | Eshan Chattopadhyay, Vipul Goyal, Xin Li |