| 2016 | Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems. | Adam Kurpisz, Samuli Leppnen, Monaldo Mastrolilli |
| 2016 | House Markets with Matroid and Knapsack Constraints. | Piotr Krysta, Jinshan Zhang |
| 2016 | Logic of Local Inference for Contextuality in Quantum Physics and Beyond. | Kohei Kishida |
| 2016 | Hardness of Approximation. | Subhash Khot |
| 2016 | An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits. | Neeraj Kayal, Chandan Saha, Sbastien Tavenas |
| 2016 | Popular Half-Integral Matchings. | Telikepalli Kavitha |
| 2016 | Closing the Gap for Makespan Scheduling via Sparsification Techniques. | Klaus Jansen, Kim-Manuel Klein, Jos Verschae |
| 2016 | Approximate Span Programs. | Tsuyoshi Ito, Stacey Jeffery |
| 2016 | Competitive Analysis of Constrained Queueing Systems. | Sungjin Im, Janardhan Kulkarni, Kamesh Munagala |
| 2016 | Dynamic Graph Stream Algorithms in o(n) Space. | Zengfeng Huang, Pan Peng |
| 2016 | On Isoperimetric Profiles and Computational Complexity. | Pavel Hrubes, Amir Yehudayoff |
| 2016 | The Decidable Properties of Subrecursive Functions. | Mathieu Hoyrup |
| 2016 | Beating the Harmonic Lower Bound for Online Bin Packing. | Sandy Heydrich, Rob van Stee |
| 2016 | Analysing Survey Propagation Guided Decimationon Random Formulas. | Samuel Hetterich |
| 2016 | Partition Bound Is Quadratically Tight for Product Distributions. | Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan |
| 2016 | Random-Edge Is Slower Than Random-Facet on Abstract Cubes. | Thomas Dueholm Hansen, Uri Zwick |
| 2016 | Approximation Algorithms for Aversion k-Clustering via Local k-Median. | Anupam Gupta, Guru Guruganesh, Melanie Schmidt |
| 2016 | Towards Tight Lower Bounds for Range Reporting on the RAM. | Allan Grnlund, Kasper Green Larsen |
| 2016 | Quasi-4-Connected Components. | Martin Grohe |
| 2016 | Boundaries of VP and VNP. | Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao |
| 2016 | A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods. | Anal Grandjean, Victor Poupet |
| 2016 | Do Distributed Differentially-Private Protocols Require Oblivious Transfer?. | Vipul Goyal, Dakshita Khurana, Ilya Mironov, Omkant Pandey, Amit Sahai |
| 2016 | Deciding Piecewise Testable Separability for Regular Tree Languages. | Jean Goubault-Larrecq, Sylvain Schmitz |
| 2016 | The Landscape of Communication Complexity Classes. | Mika Gs, Toniann Pitassi, Thomas Watson |
| 2016 | A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One. | Stefan Gller, Christoph Haase, Ranko Lazic, Patrick Totzke |