| 2016 | Linear Recognition of Almost Interval Graphs. | Yixin Cao |
| 2016 | Sampling on Lattices with Free Boundary Conditions Using Randomized Extensions. | Sarah Cannon, Dana Randall |
| 2016 | New Bounds for Approximating Extremal Distances in Undirected Graphs. | Massimo Cairo, Roberto Grossi, Romeo Rizzi |
| 2016 | An improved bound on the fraction of correctable deletions. | Boris Bukh, Venkatesan Guruswami |
| 2016 | Deterministic Algorithms for Submodular Maximization Problems. | Niv Buchbinder, Moran Feldman |
| 2016 | Recovery and Rigidity in a Regular Stochastic Block Model. | Gerandy Brito, Ioana Dumitriu, Shirshendu Ganguly, Christopher Hoffman, Linh V. Tran |
| 2016 | Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions. | Mark Braverman, Jieming Mao, S. Matthew Weinberg |
| 2016 | Clustering Problems on Sliding Windows. | Vladimir Braverman, Harry Lang, Keith D. Levin, Morteza Monemizadeh |
| 2016 | The matching problem has no small symmetric SDP. | Gbor Braun, Jonah Brown-Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz, Daniel Zink |
| 2016 | Efficient Low-Redundancy Codes for Correcting Multiple Deletions. | Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky |
| 2016 | Algorithmic Complexity of Power Law Networks. | Pawel Brach, Marek Cygan, Jakub Lacki, Piotr Sankowski |
| 2016 | On the Economic Efficiency of the Combinatorial Clock Auction. | Nicolas Bousquet, Yang Cai, Christoph Hunkenschrder, Adrian Vetta |
| 2016 | Better Distance Preservers and Additive Spanners. | Greg Bodwin, Virginia Vassilevska Williams |
| 2016 | Sparse Approximation via Generating Point Sets. | Avrim Blum, Sariel Har-Peled, Benjamin Raichel |
| 2016 | Subexponential parameterized algorithm for Interval Completion. | Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk |
| 2016 | Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems. | Ivan Bliznets, Marek Cygan, Pawel Komosa, Luks Mach, Michal Pilipczuk |
| 2016 | Random-Cluster Dynamics in ℤ | Antonio Blanca, Alistair Sinclair |
| 2016 | Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. | Jean-Franois Biasse, Fang Song |
| 2016 | Faster Fully Dynamic Matchings with Small Approximation Ratios. | Aaron Bernstein, Cliff Stein |
| 2016 | Blocking Optimal | Attila Bernth, Tams Kirly |
| 2016 | Robust positioning patterns. | Ross Berkowitz, Swastik Kopparty |
| 2016 | How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness. | Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Maxwell Young |
| 2016 | Range Predecessor and Lempel-Ziv Parsing. | Djamal Belazzougui, Simon J. Puglisi |
| 2016 | New directions in nearest neighbor searching with applications to lattice sieving. | Anja Becker, Lo Ducas, Nicolas Gama, Thijs Laarhoven |
| 2016 | Stabilizing Consensus with Many Opinions. | Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan |