| 2012 | A Dichotomy for Real Weighted Holant Problems. Sangxia Huang, Pinyan Lu |
| 2012 | A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis. Kazuhisa Seto, Suguru Tamaki |
| 2012 | A Strong Direct Product Theorem for Quantum Query Complexity. Troy Lee, Jérémie Roland |
| 2012 | A Strong Parallel Repetition Theorem for Projection Games on Expanders. Ran Raz, Ricky Rosen |
| 2012 | Algebras of Minimal Multiplicative Complexity. Markus Bläser, Bekhan Chokaev |
| 2012 | Amplifying Circuit Lower Bounds against Polynomial Time with Applications. Richard J. Lipton, Ryan Williams |
| 2012 | Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT. Paul Beame, Russell Impagliazzo, Srikanth Srinivasan |
| 2012 | Better Condensers and New Extractors from Parvaresh-Vardy Codes. Amnon Ta-Shma, Christopher Umans |
| 2012 | Combinatorial PCPs with Short Proofs. Or Meir |
| 2012 | Communication Complexity and Information Complexity: Foundations and New Directions. Toniann Pitassi |
| 2012 | Complexity Lower Bounds through Balanced Graph Properties. Guy Moshkovitz |
| 2012 | DNF Sparsification and a Faster Deterministic Counting Algorithm. Parikshit Gopalan, Raghu Meka, Omer Reingold |
| 2012 | Gaussian Noise Sensitivity and Fourier Tails. Guy Kindler, Ryan O'Donnell |
| 2012 | Hitting Set Generators for Sparse Polynomials over Any Finite Fields. Chi-Jen Lu |
| 2012 | Is Valiant-Vazirani's Isolation Probability Improvable? Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe |
| 2012 | Junto-Symmetric Functions, Hypergraph Isomorphism and Crunching. Sourav Chakraborty, Eldar Fischer, David García-Soriano, Arie Matsliah |
| 2012 | Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators. Andrew Drucker |
| 2012 | Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. Samuel R. Buss, Ryan Williams |
| 2012 | List Decoding Barnes-Wall Lattices. Elena Grigorescu, Chris Peikert |
| 2012 | Matrix Isomorphism of Matrix Lie Algebras. Joshua A. Grochow |
| 2012 | Non-malleable Extractors with Short Seeds and Applications to Privacy Amplification. Gil Cohen, Ran Raz, Gil Segev |
| 2012 | Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games. Baris Aydinlioglu, Dieter van Melkebeek |
| 2012 | On Problems as Hard as CNF-SAT. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström |
| 2012 | On Sunflowers and Matrix Multiplication. Noga Alon, Amir Shpilka, Christopher Umans |
| 2012 | On the Usefulness of Predicates. Per Austrin, Johan Håstad |
| 2012 | Parallel Approximation of Min-max Problems with Applications to Classical and Quantum Zero-Sum Games. Gus Gutoski, Xiaodi Wu |
| 2012 | Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26-29, 2012 |
| 2012 | Prospects for Geometric Complexity Theory. Peter Bürgisser |
| 2012 | Pseudorandom Generators for Read-Once ACC^0. Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan |
| 2012 | Quantum Money with Classical Verification. Dmitry Gavinsky |
| 2012 | Reductions between Expansion Problems. Prasad Raghavendra, David Steurer, Madhur Tulsiani |
| 2012 | Share Conversion and Private Information Retrieval. Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Ilan Orlov |
| 2012 | Space Complexity in Polynomial Calculus. Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen, Noga Ron-Zewi |
| 2012 | Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs. Derrick Stolee, N. V. Vinodchandran |
| 2012 | Testing List H-homomorphisms. Yuichi Yoshida |
| 2012 | The Complexity of the Separable Hamiltonian Problem. André Chailloux, Or Sattath |
| 2012 | The Hardness of Being Private. Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi |