| 2016 | 31st Conference on Computational Complexity, CCC 2016, Tokyo, Japan, May 29 - June 1, 2016 Ran Raz |
| 2016 | A Composition Theorem for Conical Juntas. Mika Göös, T. S. Jayram |
| 2016 | A Linear Time Algorithm for Quantum 2-SAT. J. Niel de Beaudrap, Sevag Gharibian |
| 2016 | Arithmetic Circuits with Locally Low Algebraic Rank. Mrinal Kumar, Shubhangi Saraf |
| 2016 | Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan |
| 2016 | Complexity Classification of Two-Qubit Commuting Hamiltonians. Adam Bouland, Laura Mancinska, Xue Zhang |
| 2016 | Decoding Reed-Muller Codes Over Product Sets. John Y. Kim, Swastik Kopparty |
| 2016 | Degree and Sensitivity: Tails of Two Distributions. Parikshit Gopalan, Rocco A. Servedio, Avi Wigderson |
| 2016 | Evolution and Computation (Invited Talk). Nisheeth K. Vishnoi |
| 2016 | Front Matter, Table of Contents, Preface, Awards, Conference Organization, External Reviewers. |
| 2016 | Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity. Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi |
| 2016 | Harmonicity and Invariance on Slices of the Boolean Cube. Yuval Filmus, Elchanan Mossel |
| 2016 | Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk |
| 2016 | Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs. Rohit Gurjar, Arpita Korwar, Nitin Saxena |
| 2016 | Invariance Principle on the Slice. Yuval Filmus, Guy Kindler, Elchanan Mossel, Karl Wimmer |
| 2016 | Learning Algorithms from Natural Proofs. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova |
| 2016 | Limits of Minimum Circuit Size Problem as Oracle. Shuichi Hirahara, Osamu Watanabe |
| 2016 | Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs. Arnab Bhattacharyya, Sivakanth Gopi |
| 2016 | Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. Andris Ambainis, Martins Kokainis, Robin Kothari |
| 2016 | New Characterizations in Turnstile Streams with Applications. Yuqing Ai, Wei Hu, Yi Li, David P. Woodruff |
| 2016 | New Extractors for Interleaved Sources. Eshan Chattopadhyay, David Zuckerman |
| 2016 | New Hardness Results for Graph and Hypergraph Colorings. Joshua Brakensiek, Venkatesan Guruswami |
| 2016 | New Non-Uniform Lower Bounds for Uniform Classes. Lance Fortnow, Rahul Santhanam |
| 2016 | Non-Malleable Extractors - New Tools and Improved Constructions. Gil Cohen |
| 2016 | On the Sum-of-Squares Degree of Symmetric Quadratic Functions. Troy Lee, Anupam Prakash, Ronald de Wolf, Henry Yuen |
| 2016 | Polynomial Bounds for Decoupling, with Applications. Ryan O'Donnell, Yu Zhao |
| 2016 | Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs |
| 2016 | Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson |
| 2016 | Pseudorandomness When the Odds are Against You. Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel |
| 2016 | Reconstruction of Real Depth-3 Circuits with Top Fan-In 2. Gaurav Sinha |
| 2016 | Sculpting Quantum Speedups. Scott Aaronson, Shalev Ben-David |
| 2016 | Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. Richard Ryan Williams |
| 2016 | Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing. Mrinal Kumar, Shubhangi Saraf |
| 2016 | Tight Bounds for Communication-Assisted Agreement Distillation. Venkatesan Guruswami, Jaikumar Radhakrishnan |
| 2016 | Tight SoS-Degree Bounds for Approximate Nash Equilibria. Aram W. Harrow, Anand Natarajan, Xiaodi Wu |
| 2016 | Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. Irit Dinur, Or Meir |
| 2016 | Understanding PPA-Completeness. Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, Zeying Xu |