| 2016 | The Non-Uniform k-Center Problem. | Deeparnab Chakrabarty, Prachi Goyal, Ravishankar Krishnaswamy |
| 2016 | On the Complexity of Grammar-Based Compression over Fixed Alphabets. | Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid |
| 2016 | Improved Bounds on the Sign-Rank of AC^0. | Mark Bun, Justin Thaler |
| 2016 | Proving the Herman-Protocol Conjecture. | Maria Bruna, Radu Grigore, Stefan Kiefer, Jol Ouaknine, James Worrell |
| 2016 | Correlation Decay and Tractability of CSPs. | Jonah Brown-Cohen, Prasad Raghavendra |
| 2016 | Information Complexity Is Computable. | Mark Braverman, Jon Schneider |
| 2016 | Coding for Interactive Communication Correcting Insertions and Deletions. | Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky |
| 2016 | Reachability in Networks of Register Protocols under Stochastic Schedulers. | Patricia Bouyer, Nicolas Markey, Mickael Randour, Arnaud Sangnier, Daniel Stan |
| 2016 | Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length: The General Purpose Analog Computer and Computable Analysis Are Two Efficiently Equivalent Models of Computations. | Olivier Bournez, Daniel Silva Graa, Amaury Pouly |
| 2016 | Voronoi Choice Games. | Meena Boppana, Rani Hod, Michael Mitzenmacher, Tom Morgan |
| 2016 | Total Space in Resolution Is at Least Width Squared. | Ilario Bonacina |
| 2016 | Thin MSO with a Probabilistic Path Quantifier. | Mikolaj Bojanczyk |
| 2016 | Subexponential Time Algorithms for Embedding H-Minor Free Graphs. | Hans L. Bodlaender, Jesper Nederlof, Tom C. van der Zanden |
| 2016 | Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. | Manuel Bodirsky, Barnaby Martin, Michael Pinsker, Andrs Pongrcz |
| 2016 | An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm. | Jaroslaw Blasiok, Jelani Nelson |
| 2016 | Bicovering: Covering Edges With Two Small Subsets of Vertices. | Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz |
| 2016 | Approximation via Correlation Decay When Strong Spatial Mixing Fails. | Ivona Bezkov, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Daniel Stefankovic |
| 2016 | Tolerant Testers of Image Properties. | Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova |
| 2016 | Supercritical Space-Width Trade-Offs for Resolution. | Christoph Berkholz, Jakob Nordstrm |
| 2016 | Fine-Grained Complexity Analysis of Two Classic TSP Variants. | Mark de Berg, Kevin Buchin, Bart M. P. Jansen, Gerhard J. Woeginger |
| 2016 | Bounds on the Voter Model in Dynamic Networks. | Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, Frederik Mallmann-Trenn |
| 2016 | Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time. | Petra Berenbrink, Tom Friedetzky, George Giakkoupis, Peter Kling |
| 2016 | On Percolation and NP-Hardness. | Huck Bennett, Daniel Reichman, Igor Shinkar |
| 2016 | Randomized Query Complexity of Sabotaged and Composed Functions. | Shalev Ben-David, Robin Kothari |
| 2016 | Minimizing Resources of Sweeping and Streaming String Transducers. | Flix Baschenis, Olivier Gauwin, Anca Muscholl, Gabriele Puppis |