| 2016 | The Constant Inapproximability of the Parameterized Dominating Set Problem. | Yijia Chen, Bingkai Lin |
| 2016 | Fourier-Sparse Interpolation without a Frequency Gap. | Xue Chen, Daniel M. Kane, Eric Price, Zhao Song |
| 2016 | Decremental Single-Source Reachability and Strongly Connected Components in (m√n) Total Update Time. | Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Lacki, Nikos Parotsidis |
| 2016 | Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification Protocols. | Eshan Chattopadhyay, Xin Li |
| 2016 | A PTAS for the Steiner Forest Problem in Doubling Metrics. | T.-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang |
| 2016 | An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. | Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie |
| 2016 | Strong Fooling Sets for Multi-player Communication with Applications to Deterministic Estimation of Stream Statistics. | Amit Chakrabarti, Sagar Kale |
| 2016 | No Occurrence Obstructions in Geometric Complexity Theory. | Peter Brgisser, Christian Ikenmeyer, Greta Panova |
| 2016 | Zero-Knowledge Proof Systems for QMA. | Anne Broadbent, Zhengfeng Ji, Fang Song, John Watrous |
| 2016 | Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product. | Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams |
| 2016 | Edit Distance: Sketching, Streaming, and Document Exchange. | Djamal Belazzougui, Qin Zhang |
| 2016 | A New Framework for Distributed Submodular Maximization. | Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen, Justin Ward |
| 2016 | A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. | Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin |
| 2016 | An Algorithm for Komls Conjecture Matching Banaszczyk's Bound. | Nikhil Bansal, Daniel Dadush, Shashwat Garg |
| 2016 | Which Regular Expression Patterns Are Hard to Match? | Arturs Backurs, Piotr Indyk |
| 2016 | A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents. | Haris Aziz, Simon Mackenzie |
| 2016 | Online Algorithms for Covering and Packing Problems with Convex Objectives. | Yossi Azar, Niv Buchbinder, T.-H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, Debmalya Panigrahi |
| 2016 | Separations in Communication Complexity Using Cheat Sheets and Information Complexity. | Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Gs, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha |
| 2016 | Polynomial Representations of Threshold Functions and Algorithmic Applications. | Josh Alman, Timothy M. Chan, R. Ryan Williams |
| 2016 | On Fully Dynamic Graph Sparsifiers. | Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, Richard Peng |
| 2016 | Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms. | Amir Abboud, Sren Dahlgaard |
| 2015 | An O(1)-Approximation for Minimum Spanning Tree Interdiction. | Rico Zenklusen |
| 2015 | Sample (x) = (a*x<=t) is a Distinguisher with Probability 1/8. | Mikkel Thorup |
| 2015 | Approximating ATSP by Relaxing Connectivity. | Ola Svensson |
| 2015 | Guaranteed Matrix Completion via Nonconvex Factorization. | Ruoyu Sun, Zhi-Quan Luo |