| 2016 | A Note On Spectral Clustering. | Pavel Kolev, Kurt Mehlhorn |
| 2016 | A Streaming Algorithm for the Undirected Longest Path Problem. | Lasse Kliemann, Christian Schielke, Anand Srivastav |
| 2016 | Hardness of Bipartite Expansion. | Subhash Khot, Rishi Saket |
| 2016 | Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions. | Thomas Kesselheim, Andreas Tnnis |
| 2016 | Faster Worst Case Deterministic Dynamic Connectivity. | Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup |
| 2016 | Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time. | Matti Karppa, Petteri Kaski, Jukka Kohonen, Padraig Cathin |
| 2016 | Faster External Memory LCP Array Construction. | Juha Krkkinen, Dominik Kempa |
| 2016 | Every Property Is Testable on a Natural Class of Scale-Free Multigraphs. | Hiro Ito |
| 2016 | A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges. | Chien-Chung Huang, Sebastian Ott |
| 2016 | epsilon-Kernel Coresets for Stochastic Points. | Lingxiao Huang, Jian Li, Jeff M. Phillips, Haitao Wang |
| 2016 | Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning. | Monika Henzinger, Stefan Neumann |
| 2016 | Packing and Covering with Non-Piercing Regions. | Sathish Govindarajan, Rajiv Raman, Saurabh Ray, Aniket Basu Roy |
| 2016 | Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time. | Gramoz Goranci, Monika Henzinger, Mikkel Thorup |
| 2016 | How Hard is it to Find (Honest) Witnesses?. | Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat |
| 2016 | Streaming Pattern Matching with d Wildcards. | Shay Golan, Tsvi Kopelowitz, Ely Porat |
| 2016 | 2-Connectivity in Directed Graphs. | Loukas Georgiadis, Giuseppe F. Italiano, Nikos Parotsidis |
| 2016 | Streaming Property Testing of Visibly Pushdown Languages. | Nathanal Franois, Frdric Magniez, Michel de Rougemont, Olivier Serre |
| 2016 | New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness. | Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase |
| 2016 | Distributed Signaling Games. | Moran Feldman, Moshe Tennenholtz, Omri Weinstein |
| 2016 | A Constant Approximation Algorithm for Scheduling Packets on Line Networks. | Guy Even, Moti Medina, Adi Rosn |
| 2016 | Counting Linear Extensions: Parameterizations by Treewidth. | Eduard Eiben, Robert Ganian, Kustaa Kangas, Sebastian Ordyniak |
| 2016 | BlockQuicksort: Avoiding Branch Mispredictions in Quicksort. | Stefan Edelkamp, Armin Wei |
| 2016 | On the Power of Advice and Randomization for Online Bipartite Matching. | Christoph Drr, Christian Konrad, Marc P. Renault |
| 2016 | Exponential Time Paradigms Through the Polynomial Time Lens. | Andrew Drucker, Jesper Nederlof, Rahul Santhanam |
| 2016 | SimBa: An Efficient Tool for Approximating Rips-Filtration Persistence via Simplicial Batch-Collapse. | Tamal K. Dey, Dayu Shi, Yusu Wang |