| 2016 | Streaming algorithms for embedding and computing edit distance in the low distance regime. | Diptarka Chakraborty, Elazar Goldenberg, Michal Kouck |
| 2016 | A duality based unified approach to Bayesian mechanism design. | Yang Cai, Nikhil R. Devanur, S. Matthew Weinberg |
| 2016 | Parallel algorithms for select and partition with noisy comparisons. | Mark Braverman, Jieming Mao, S. Matthew Weinberg |
| 2016 | Communication lower bounds for statistical estimation problems via a distributed data processing inequality. | Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff |
| 2016 | Constant-rate coding for multiparty interactive communication is impossible. | Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler |
| 2016 | Beating CountSketch for heavy hitters in insertion streams. | Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff |
| 2016 | A lower bound for the distributed Lovsz local lemma. | Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiinen, Joel Rybicki, Jukka Suomela, Jara Uitto |
| 2016 | Optimal principal component analysis in distributed and streaming models. | Christos Boutsidis, David P. Woodruff, Peilin Zhong |
| 2016 | New deterministic approximation algorithms for fully dynamic matching. | Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai |
| 2016 | Deterministic decremental single source shortest paths: beyond the o(mn) bound. | Aaron Bernstein, Shiri Chechik |
| 2016 | Contention resolution with log-logstar channel accesses. | Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young |
| 2016 | A polynomial lower bound for testing monotonicity. | Aleksandrs Belovs, Eric Blais |
| 2016 | A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting. | MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, Dniel Marx |
| 2016 | Fault tolerant subgraph for single source reachability: generic and optimal. | Surender Baswana, Keerti Choudhary, Liam Roditty |
| 2016 | Algorithmic stability for adaptive data analysis. | Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, Jonathan R. Ullman |
| 2016 | Lift-and-round to improve weighted completion time on unrelated machines. | Nikhil Bansal, Aravind Srinivasan, Ola Svensson |
| 2016 | Graph isomorphism in quasipolynomial time [extended abstract]. | Lszl Babai |
| 2016 | A discrete and bounded envy-free cake cutting protocol for four agents. | Haris Aziz, Simon Mackenzie |
| 2016 | Tight bounds for single-pass streaming complexity of the set cover problem. | Sepehr Assadi, Sanjeev Khanna, Yang Li |
| 2016 | Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations. | Gilad Asharov, Moni Naor, Gil Segev, Ido Shahaf |
| 2016 | Almost tight bounds for eliminating depth cycles in three dimensions. | Boris Aronov, Micha Sharir |
| 2016 | Algebraic attacks against random local functions and their countermeasures. | Benny Applebaum, Shachar Lovett |
| 2016 | Separations in query complexity based on pointer functions. | Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs |
| 2016 | Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. | Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams |
| 2016 | The 4/3 additive spanner exponent is tight. | Amir Abboud, Greg Bodwin |