| 2016 | Dynamic DFS in Undirected Graphs: breaking the O( | Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, Shahbaz Khan |
| 2016 | On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion. | Yair Bartal, Arnold Filtser, Ofer Neiman |
| 2016 | Improved Approximation for Vector Bin Packing. | Nikhil Bansal, Marek Elis, Arindam Khan |
| 2016 | Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions. | Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer |
| 2016 | Nearly-optimal bounds for sparse recovery in generic norms, with applications to | Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, David P. Woodruff |
| 2016 | Make-to-Order Integrated Scheduling and Distribution. | Yossi Azar, Amir Epstein, Lukasz Jez, Adi Vardi |
| 2016 | Packing Small Vectors. | Yossi Azar, Ilan Reuven Cohen, Amos Fiat, Alan Roytman |
| 2016 | Balanced Allocation: Patience is not a Virtue. | John Augustine, William K. Moses Jr., Amanda Redlich, Eli Upfal |
| 2016 | Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model. | Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev |
| 2016 | A Fast and Simple Algorithm for Computing Approximate Euclidean Minimum Spanning Trees. | Sunil Arya, David M. Mount |
| 2016 | Finding Perfect Matchings in Bipartite Hypergraphs. | Chidambaram Annamalai |
| 2016 | Windrose Planarity: Embedding Graphs with Direction-Constrained Edges. | Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Valentino Di Donato, Philipp Kindermann, Gnter Rote, Ignaz Rutter |
| 2016 | Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. | Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf |
| 2016 | Simpler, faster and shorter labels for distances in graphs. | Stephen Alstrup, Cyril Gavoille, Esben Bistrup Halvorsen, Holger Petersen |
| 2016 | On the maximum quartet distance between phylogenetic trees. | Noga Alon, Humberto Naves, Benny Sudakov |
| 2016 | Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver. | Zeyuan Allen Zhu, Yin Tat Lee, Lorenzo Orecchia |
| 2016 | Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time. | Kunal Agrawal, Jing Li, Kefu Lu, Benjamin Moseley |
| 2016 | An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles. | Pankaj K. Agarwal, Kyle Fox, Oren Salzman |
| 2016 | Focused Stochastic Local Search and the Lovsz Local Lemma. | Dimitris Achlioptas, Fotis Iliopoulos |
| 2016 | Bounds for Random Constraint Satisfaction Problems via Spatial Coupling. | Dimitris Achlioptas, Seyed Hamed Hassani, Nicolas Macris, Rdiger L. Urbanke |
| 2016 | On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs. | Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew V. Goldberg, Renato F. Werneck |
| 2016 | Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. | Amir Abboud, Virginia Vassilevska Williams, Joshua R. Wang |
| 2016 | Subtree Isomorphism Revisited. | Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir |
| 2016 | Error Amplification for Pairwise Spanner Lower Bounds. | Amir Abboud, Greg Bodwin |
| 2016 | Designing Networks with Good Equilibria under Uncertainty. | George Christodoulou, Alkmini Sgouritsa |