| 2016 | Algorithms and Adaptivity Gaps for Stochastic Probing. | Anupam Gupta, Viswanath Nagarajan, Sahil Singla |
| 2016 | Towards Optimal Algorithms for Prediction with Expert Advice. | Nick Gravin, Yuval Peres, Balasubramanian Sivan |
| 2016 | Time vs. Information Tradeoffs for Leader Election in Anonymous Trees. | Christian Glacet, Avery Miller, Andrzej Pelc |
| 2016 | Computing in continuous space with self-assembling polygonal tiles (extended abstract). | Oscar Gilbert, Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers |
| 2016 | Communication Complexity of Permutation-Invariant Functions. | Badih Ghazi, Pritish Kamath, Madhu Sudan |
| 2016 | Communication with Contextual Uncertainty. | Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan |
| 2016 | Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut. | Mohsen Ghaffari, Bernhard Haeupler |
| 2016 | An Improved Distributed Algorithm for Maximal Independent Set. | Mohsen Ghaffari |
| 2016 | Towards Optimal Deterministic Coding for Interactive Communication. | Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson |
| 2016 | Permutation patterns are hard to count. | Scott Garrabrant, Igor Pak |
| 2016 | Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee. | Shivam Garg, Geevarghese Philip |
| 2016 | Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting. | Robert Ganian, M. S. Ramanujan, Stefan Szeider |
| 2016 | The complexity of approximately counting in 2-spin systems on | Andreas Galanis, Leslie Ann Goldberg |
| 2016 | Online Contention Resolution Schemes. | Moran Feldman, Ola Svensson, Rico Zenklusen |
| 2016 | The Complexity of All-switches Strategy Improvement. | John Fearnley, Rahul Savani |
| 2016 | Treetopes and their Graphs. | David Eppstein |
| 2016 | On the switch Markov chain for perfect matchings. | Martin E. Dyer, Mark Jerrum, Haiko Mller |
| 2016 | An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market. | Ran Duan, Jugal Garg, Kurt Mehlhorn |
| 2016 | Clustering time series under the Frchet distance. | Anne Driemel, Amer Krivosija, Christian Sohler |
| 2016 | Undirected Graph Exploration with ⊝(log log | Yann Disser, Jan Hackfeld, Max Klimm |
| 2016 | Approximating Low-Stretch Spanners. | Michael Dinitz, Zeyu Zhang |
| 2016 | Multiscale Mapper: Topological Summarization via Codomain Covers. | Tamal K. Dey, Facundo Mmoli, Yusu Wang |
| 2016 | Online Degree-Bounded Steiner Network Design. | Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat |
| 2016 | Species Trees from Gene Trees Despite a High Rate of Lateral Genetic Transfer: A Tight Bound (Extended Abstract). | Constantinos Daskalakis, Sebastien Roch |
| 2016 | The Power of Two Choices with Simple Tabulation. | Sren Dahlgaard, Mathias Bk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup |