| 2012 | (Leveled) fully homomorphic encryption without bootstrapping. Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan |
| 2012 | Algorithms on evolving graphs. Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal, Fabio Vandin |
| 2012 | Approximately optimal mechanism design via differential privacy. Kobbi Nissim, Rann Smorodinsky, Moshe Tennenholtz |
| 2012 | Bounds on locally testable codes with unique tests. Gillat Kol, Ran Raz |
| 2012 | Compressed matrix multiplication. Rasmus Pagh |
| 2012 | Crowdsourced Bayesian auctions. Pablo Azar, Jing Chen, Silvio Micali |
| 2012 | Distribution free evolvability of polynomial functions over all convex loss functions. Paul Valiant |
| 2012 | Dynamics of prisoner's dilemma and the evolution of cooperation on networks. Vahideh H. Manshadi, Amin Saberi |
| 2012 | Fairness through awareness. Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel |
| 2012 | From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer |
| 2012 | From randomizing polynomials to parallel algorithms. Yuval Ishai, Eyal Kushilevitz, Anat Paskin-Cherniavsky |
| 2012 | Gadgets and anti-gadgets leading to a complexity dichotomy. Jin-Yi Cai, Michael Kowalczyk, Tyson Williams |
| 2012 | Graph densification. Moritz Hardt, Nikhil Srivastava, Madhur Tulsiani |
| 2012 | High-confidence predictions under adversarial uncertainty. Andrew Drucker |
| 2012 | Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012 Shafi Goldwasser |
| 2012 | Learning hurdles for sleeping experts. Varun Kanade, Thomas Steinke |
| 2012 | Linear programming, width-1 CSPs, and robust satisfaction. Gábor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida, Yuan Zhou |
| 2012 | Linear time decoding of regular expander codes. Michael Viderman |
| 2012 | List decoding subspace codes from insertions and deletions. Venkatesan Guruswami, Srivatsan Narayanan, Carol Wang |
| 2012 | Marginal hitting sets imply super-polynomial lower bounds for permanent. Maurice J. Jansen, Rahul Santhanam |
| 2012 | Mechanism design with approximate valuations. Alessandro Chiesa, Silvio Micali, Zeyuan Allen Zhu |
| 2012 | Multicommodity flows and cuts in polymatroidal networks. Chandra Chekuri, Sreeram Kannan, Adnan Raja, Pramod Viswanath |
| 2012 | No justified complaints: on fair sharing of multiple resources. Danny Dolev, Dror G. Feitelson, Joseph Y. Halpern, Raz Kupferman, Nathan Linial |
| 2012 | Noise vs computational intractability in dynamics. Mark Braverman, Alexander Grigo, Cristobal Rojas |
| 2012 | On beating the hybrid argument. Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola |
| 2012 | On persistent homotopy, knotted complexes and the Alexander module. David Letscher |
| 2012 | On the degree of univariate polynomials over the integers. Gil Cohen, Amir Shpilka, Avishay Tal |
| 2012 | Paging for multi-core shared caches. Alejandro López-Ortiz, Alejandro Salinger |
| 2012 | Practical verified computation with streaming interactive proofs. Graham Cormode, Michael Mitzenmacher, Justin Thaler |
| 2012 | Quantum interactive proofs with weak error bounds. Tsuyoshi Ito, Hirotada Kobayashi, John Watrous |
| 2012 | Quantum money from knots. Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Peter W. Shor |
| 2012 | Quantum rejection sampling. Maris Ozols, Martin Roetteler, Jérémie Roland |
| 2012 | Quantum strategic game theory. Shengyu Zhang |
| 2012 | Restriction access. Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff |
| 2012 | Sherali-Adams relaxations and indistinguishability in counting logics. Albert Atserias, Elitza N. Maneva |
| 2012 | Spectral sparsification via random spanners. Michael Kapralov, Rina Panigrahy |
| 2012 | Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure. Bohua Zhan, Shelby Kimmel, Avinatan Hassidim |
| 2012 | Targeted malleability: homomorphic encryption for restricted computations. Dan Boneh, Gil Segev, Brent Waters |
| 2012 | The curse of simultaneity. Renato Paes Leme, Vasilis Syrgkanis, Éva Tardos |
| 2012 | Towards deterministic tree code constructions. Mark Braverman |