| 2015 | 30th Conference on Computational Complexity, CCC 2015, Portland, Oregon, USA, June 17-19, 2015 David Zuckerman |
| 2015 | A Characterization of Hard-to-cover CSPs. Amey Bhangale, Prahladh Harsha, Girish Varma |
| 2015 | A Depth-Five Lower Bound for Iterated Matrix Multiplication. Suman K. Bera, Amit Chakrabarti |
| 2015 | A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds. Mladen Miksa, Jakob Nordström |
| 2015 | A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting. Daniel M. Kane |
| 2015 | Adaptivity Helps for Testing Juntas. Rocco A. Servedio, Li-Yang Tan, John Wright |
| 2015 | An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. Venkatesan Guruswami, Ameya Velingker |
| 2015 | Circuits with Medium Fan-In. Pavel Hrubes, Anup Rao |
| 2015 | Correlation Bounds Against Monotone NC^1. Benjamin Rossman |
| 2015 | Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs. Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf |
| 2015 | Factors of Low Individual Degree Polynomials. Rafael Mendes de Oliveira |
| 2015 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2015 | Generalized Quantum Arthur-Merlin Games. Hirotada Kobayashi, François Le Gall, Harumichi Nishimura |
| 2015 | How to Compress Asymmetric Communication. Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao |
| 2015 | Identifying an Honest EXP^NP Oracle Among Many. Shuichi Hirahara |
| 2015 | Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions (Extended Abstract). Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang |
| 2015 | Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity. Alex Samorodnitsky, Ilya D. Shkredov, Sergey Yekhanin |
| 2015 | Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin. Neeraj Kayal, Chandan Saha |
| 2015 | Majority is Incompressible by AC^0[p] Circuits. Igor Carboni Oliveira, Rahul Santhanam |
| 2015 | Non-Commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs. Fu Li, Iddo Tzameret, Zhengyu Wang |
| 2015 | Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds. Abhishek Bhowmick, Shachar Lovett |
| 2015 | On Randomness Extraction in AC0. Oded Goldreich, Emanuele Viola, Avi Wigderson |
| 2015 | On the (Non) NP-Hardness of Computing Circuit Complexity. Cody D. Murray, Richard Ryan Williams |
| 2015 | Parallel Repetition for Entangled k-player Games via Fast Quantum Search. Kai-Min Chung, Xiaodi Wu, Henry S. Yuen |
| 2015 | Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness. Anup Rao, Amir Yehudayoff |
| 2015 | Strong Locally Testable Codes with Relaxed Local Decoders. Oded Goldreich, Tom Gur, Ilan Komargodski |
| 2015 | Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. Rafael Oliveira, Amir Shpilka, Ben Lee Volk |
| 2015 | The List-Decoding Size of Fourier-Sparse Boolean Functions. Ishay Haviv, Oded Regev |
| 2015 | The Space Complexity of Cutting Planes Refutations. Nicola Galesi, Pavel Pudlák, Neil Thapen |
| 2015 | Tight Size-Degree Bounds for Sums-of-Squares Proofs. Massimo Lauria, Jakob Nordström |
| 2015 | Upper Bounds on Quantum Query Complexity Inspired by the Elitzur-Vaidman Bomb Tester. Cedric Yen-Yu Lin, Han-Hsuan Lin |
| 2015 | Verifiable Stream Computation and Arthur-Merlin Communication. Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian |