| 2013 | A Derandomized Switching Lemma and an Improved Derandomization of AC0. Luca Trevisan, Tongke Xue |
| 2013 | An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability. Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, Osamu Watanabe |
| 2013 | Approaching the Chasm at Depth Four. Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi |
| 2013 | Approximating Boolean Functions with Depth-2 Circuits. Eric Blais, Li-Yang Tan |
| 2013 | Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits. Yasuhiro Takahashi, Seiichiro Tani |
| 2013 | Composition Limits and Separating Examples for Some Boolean Function Complexity Measures. Justin Gilmer, Michael E. Saks, Srikanth Srinivasan |
| 2013 | Constructing Hard Functions Using Learning Algorithms. Adam R. Klivans, Pravesh Kothari, Igor C. Oliveira |
| 2013 | Covering CSPs. Irit Dinur, Gillat Kol |
| 2013 | Formulas are Exponentially Stronger than Monotone Circuits in Non-commutative Setting. Pavel Hrubes, Amir Yehudayoff |
| 2013 | How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions? Andris Ambainis, Ronald de Wolf |
| 2013 | Just a Pebble Game. Siu Man Chan |
| 2013 | LS+ Lower Bounds from Pairwise Independence. Madhur Tulsiani, Pratik Worah |
| 2013 | Lower Bounds for DNF-refutations of a Relativized Weak Pigeonhole Principle. Albert Atserias, Moritz Müller, Sergi Oliva |
| 2013 | On Medium-Uniformity and Circuit Lower Bounds. Rahul Santhanam, Ryan Williams |
| 2013 | On Rigid Matrices and U-polynomials. Noga Alon, Gil Cohen |
| 2013 | On the Lattice Smoothing Parameter Problem. Kai-Min Chung, Daniel Dadush, Feng-Hao Liu, Chris Peikert |
| 2013 | On the Parameterized and Approximation Hardness of Metric Dimension. Sepp Hartung, André Nichterlein |
| 2013 | On the Power of Non-adaptive Learning Graphs. Aleksandrs Belovs, Ansis Rosmanis |
| 2013 | Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover. Sushant Sachdeva, Rishi Saket |
| 2013 | Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013 |
| 2013 | Quantum XOR Games. Oded Regev, Thomas Vidick |
| 2013 | Random Arithmetic Formulas Can Be Reconstructed Efficiently. Ankit Gupta, Neeraj Kayal, Youming Qiao |
| 2013 | Shared Randomness and Quantum Communication in the Multi-party Model. Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang |
| 2013 | Short Lists with Short Programs in Short Time. Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand |
| 2013 | Strong LTCs with Inverse Polylogarithmic Rate and Soundness. Michael Viderman |
| 2013 | Superlinear Lower Bounds for Multipass Graph Processing. Venkatesan Guruswami, Krzysztof Onak |
| 2013 | The Correct Exponent for the Gotsman-Linial Conjecture. Daniel M. Kane |
| 2013 | The Distinguishability of Product Distributions by Read-Once Branching Programs. John P. Steinberger |
| 2013 | Towards a Reverse Newman's Theorem in Interactive Information Complexity. Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin |
| 2013 | Two-Message Quantum Interactive Proofs and the Quantum Separability Problem. Patrick M. Hayden, Kevin Milner, Mark M. Wilde |