| 2016 | A PAC Approach to Application-Specific Algorithm Selection. Rishi Gupta, Tim Roughgarden |
| 2016 | An Axiomatic Approach to Community Detection. Christian Borgs, Jennifer T. Chayes, Adrian Marple, Shang-Hua Teng |
| 2016 | Auction Revenue in the General Spiteful-Utility Model. Jing Chen, Silvio Micali |
| 2016 | Can Almost Everybody be Almost Happy? Yakov Babichenko, Christos H. Papadimitriou, Aviad Rubinstein |
| 2016 | Coordination Complexity: Small Information Coordinating Large Populations. Rachel Cummings, Katrina Ligett, Jaikumar Radhakrishnan, Aaron Roth, Zhiwei Steven Wu |
| 2016 | Cryptography for Parallel RAM from Indistinguishability Obfuscation. Yu-Chi Chen, Sherman S. M. Chow, Kai-Min Chung, Russell W. F. Lai, Wei-Kai Lin, Hong-Sheng Zhou |
| 2016 | Distribution Design. Amos Beimel, Ariel Gabizon, Yuval Ishai, Eyal Kushilevitz |
| 2016 | Energy-Efficient Algorithms. Erik D. Demaine, Jayson Lynch, Geronimo J. Mirano, Nirvan Tyagi |
| 2016 | From Nash Equilibria to Chain Recurrent Sets: Solution Concepts and Topology. Christos H. Papadimitriou, Georgios Piliouras |
| 2016 | Fully Succinct Garbled RAM. Ran Canetti, Justin Holmgren |
| 2016 | How To Bootstrap Anonymous Communication. Sune K. Jakobsen, Claudio Orlandi |
| 2016 | How to Incentivize Data-Driven Collaboration Among Competing Parties. Pablo Daniel Azar, Shafi Goldwasser, Sunoo Park |
| 2016 | Information Complexity Density and Simulation of Protocols. Himanshu Tyagi, Shaileshh Bojja Venkatakrishnan, Pramod Viswanath, Shun Watanabe |
| 2016 | Is There an Oblivious RAM Lower Bound? Elette Boyle, Moni Naor |
| 2016 | Local Algorithms for Block Models with Side Information. Elchanan Mossel, Jiaming Xu |
| 2016 | Lower Bounds: From Circuits to QBF Proof Systems. Olaf Beyersdorff, Ilario Bonacina, Leroy Chew |
| 2016 | Mechanisms With Costly Knowledge. Atalay Mert Ileri, Silvio Micali |
| 2016 | Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility. Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider |
| 2016 | Obfuscating Conjunctions under Entropic Ring LWE. Zvika Brakerski, Vinod Vaikuntanathan, Hoeteck Wee, Daniel Wichs |
| 2016 | On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract]. Roei Tell |
| 2016 | On Hardness of Approximating the Parameterized Clique Problem. Subhash Khot, Igor Shinkar |
| 2016 | On Sketching Quadratic Forms. Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang |
| 2016 | On a Natural Dynamics for Linear Programming. Damian Straszak, Nisheeth K. Vishnoi |
| 2016 | On the Computational Complexity of Limit Cycles in Dynamical Systems. Christos H. Papadimitriou, Nisheeth K. Vishnoi |
| 2016 | On the Computational Complexity of Optimal Simple Mechanisms. Aviad Rubinstein |
| 2016 | On the Space Complexity of Linear Programming with Preprocessing. Yael Tauman Kalai, Ran Raz, Oded Regev |
| 2016 | Permanent v. Determinant: An Exponential Lower Bound Assuming Symmetry. Joseph M. Landsberg, Nicolas Ressayre |
| 2016 | Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016 Madhu Sudan |
| 2016 | Rational Proofs with Multiple Provers. Jing Chen, Samuel McCauley, Shikha Singh |
| 2016 | Sampling Correctors. Clément L. Canonne, Themis Gouleakis, Ronitt Rubinfeld |
| 2016 | Satisfiability on Mixed Instances. Ruiwen Chen, Rahul Santhanam |
| 2016 | Secure Multiparty Computation with General Interaction Patterns. Shai Halevi, Yuval Ishai, Abhishek Jain, Eyal Kushilevitz, Tal Rabin |
| 2016 | Simultaneous Private Learning of Multiple Concepts. Mark Bun, Kobbi Nissim, Uri Stemmer |
| 2016 | Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions. Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson |
| 2016 | Spectral Embedding of k-Cliques, Graph Partitioning and k-Means. Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop |
| 2016 | Strategic Classification. Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, Mary Wootters |
| 2016 | The Complexity of DNF of Parities. Gil Cohen, Igor Shinkar |
| 2016 | The Space "Just Above" BQP. Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee |
| 2016 | Time-Lock Puzzles from Randomized Encodings. Nir Bitansky, Shafi Goldwasser, Abhishek Jain, Omer Paneth, Vinod Vaikuntanathan, Brent Waters |
| 2016 | Timeability of Extensive-Form Games. Sune K. Jakobsen, Troels Bjerre Sørensen, Vincent Conitzer |
| 2016 | Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds. Alexander Golovnev, Alexander S. Kulikov |