| 2016 | Semi-Streaming Algorithms for Annotated Graph Streams. | Justin Thaler |
| 2016 | Lower Bounds for the Approximate Degree of Block-Composed Functions. | Justin Thaler |
| 2016 | New Interpretation and Generalization of the Kameda-Weiner Method. | Hellis Tamm |
| 2016 | On the Sensitivity Conjecture. | Avishay Tal |
| 2016 | All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing. | Christian Sommer |
| 2016 | Deciding the Topological Complexity of Bchi Languages. | Michal Skrzypczak, Igor Walukiewicz |
| 2016 | Compute Choice. | Devavrat Shah |
| 2016 | A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest. | Frans Schalekamp, Anke van Zuylen, Suzanne van der Ster |
| 2016 | Algorithmic Complexity for the Realization of an Effective Subshift By a Sofic. | Mathieu Sablik, Michael Schraudner |
| 2016 | Nesting Depth of Operators in Graph Database Queries: Expressiveness vs. Evaluation Complexity. | M. Praveen, B. Srivathsan |
| 2016 | Rnyi Information Complexity and an Information Theoretic Characterization of the Partition Bound. | Manoj M. Prabhakaran, Vinod M. Prabhakaran |
| 2016 | Near Optimal Adjacency Labeling Schemes for Power-Law Graphs. | Casper Petersen, Noy Rotbart, Jakob Grue Simonsen, Christian Wulff-Nilsen |
| 2016 | Mixing Time of Markov Chains, Dynamical Systems and Evolution. | Ioannis Panageas, Nisheeth K. Vishnoi |
| 2016 | Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation. | Jesper W. Mikkelsen |
| 2016 | Quasimetric Embeddings and Their Applications. | Facundo Mmoli, Anastasios Sidiropoulos, Vijay Sridhar |
| 2016 | Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth. | Dniel Marx, Valia Mitsou |
| 2016 | A Fast Distributed Stateless Algorithm for alpha-Fair Packing Problems. | Jelena Marasevic, Clifford Stein, Gil Zussman |
| 2016 | Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time. | Michael W. Mahoney, Satish Rao, Di Wang, Peng Zhang |
| 2016 | Provably Secure Virus Detection: Using The Observer Effect Against Malware. | Richard J. Lipton, Rafail Ostrovsky, Vassilis Zikas |
| 2016 | Deterministic Time-Space Trade-Offs for k-SUM. | Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams |
| 2016 | Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions. | Benot Libert, Somindu C. Ramanna, Moti Yung |
| 2016 | Formally Verifying a Compiler: What Does It Mean, Exactly? | Xavier Leroy |
| 2016 | The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. | Kasper Green Larsen, Jelani Nelson |
| 2016 | Approximating Directed Steiner Problems via Tree Embedding. | Bundit Laekhanukit |
| 2016 | Model Checking and Strategy Synthesis for Stochastic Games: From Theory to Practice. | Marta Z. Kwiatkowska |