| 2016 | Approximating capacitated | Shi Li |
| 2016 | Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile. | Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee |
| 2016 | Characterisation of Strongly Stable Matchings. | Adam Kunysz, Katarzyna E. Paluch, Pratik Ghosal |
| 2016 | Higher Lower Bounds from the 3SUM Conjecture. | Tsvi Kopelowitz, Seth Pettie, Ely Porat |
| 2016 | Approximation of non-boolean 2CSP. | Guy Kindler, Alexandra Kolla, Luca Trevisan |
| 2016 | Persistent Homology and Nested Dissection. | Michael Kerber, Donald R. Sheehy, Primoz Skraba |
| 2016 | A Faster Subquadratic Algorithm for Finding Outlier Correlations. | Matti Karppa, Petteri Kaski, Jukka Kohonen |
| 2016 | Distance in the Forest Fire Model How far are you from Eve? | Varun Kanade, Reut Levi, Zvi Lotker, Frederik Mallmann-Trenn, Claire Mathieu |
| 2016 | An Improved Approximation Guarantee for the Maximum Budgeted Allocation Problem. | Christos Kalaitzis |
| 2016 | Sparsity and dimension. | Gwenal Joret, Piotr Micek, Veit Wiechert |
| 2016 | Constructive algorithm for path-width of matroids. | Jisu Jeong, Eun Jung Kim, Sang-il Oum |
| 2016 | Approximation schemes for machine scheduling with resource (in-)dependent processing times. | Klaus Jansen, Marten Maack, Malin Rau |
| 2016 | Finding a Stable Allocation in Polymatroid Intersection. | Satoru Iwata, Yu Yokoi |
| 2016 | Improved Approximation Algorithms for | Satoru Iwata, Shin-ichi Tanigawa, Yuichi Yoshida |
| 2016 | Weighted dynamic finger in binary search trees. | John Iacono, Stefan Langerman |
| 2016 | Canonical Paths for MCMC: from Art to Science. | Lingxiao Huang, Pinyan Lu, Chihao Zhang |
| 2016 | Exact and Approximation Algorithms for Weighted Matroid Intersection. | Chien-Chung Huang, Naonori Kakimura, Naoyuki Kamiyama |
| 2016 | Jointly Private Convex Programming. | Justin Hsu, Zhiyi Huang, Aaron Roth, Zhiwei Steven Wu |
| 2016 | The Adversarial Noise Threshold for Distributed Protocols. | William M. Hoza, Leonard J. Schulman |
| 2016 | On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique. | Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm |
| 2016 | An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra. | Robert Hildebrand, Robert Weismantel, Kevin Zemmer |
| 2016 | The Restricted Isometry Property of Subsampled Fourier Matrices. | Ishay Haviv, Oded Regev |
| 2016 | Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution. | David G. Harris, Aravind Srinivasan |
| 2016 | Approximating the | Sariel Har-Peled, Haim Kaplan, Micha Sharir |
| 2016 | Nearly Optimal NP-Hardness of Unique Coverage. | Venkatesan Guruswami, Euiwoong Lee |