| 2012 | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. | Adriana Lpez-Alt, Eran Tromer, Vinod Vaikuntanathan |
| 2012 | Design extractors, non-malleable condensers and privacy amplification. | Xin Li |
| 2012 | Prior-free auctions with ordered bidders. | Stefano Leonardi, Tim Roughgarden |
| 2012 | Multi-way spectral partitioning and higher-order cheeger inequalities. | James R. Lee, Shayan Oveis Gharan, Luca Trevisan |
| 2012 | The cell probe complexity of dynamic range counting. | Kasper Green Larsen |
| 2012 | Probabilistic existence of rigid combinatorial structures. | Greg Kuperberg, Shachar Lovett, Ron Peled |
| 2012 | Matroid prophet inequalities. | Robert Kleinberg, S. Matthew Weinberg |
| 2012 | 2 | Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi |
| 2012 | Faster approximate multicommodity flow using quadratically coupled flows. | Jonathan A. Kelner, Gary L. Miller, Richard Peng |
| 2012 | Affine projections of polynomials: extended abstract. | Neeraj Kayal |
| 2012 | Edge transitive ramanujan graphs and symmetric LDPC good codes. | Tali Kaufman, Alexander Lubotzky |
| 2012 | On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity. | Trinh Huynh, Jakob Nordstrm |
| 2012 | Short proofs for the determinant identities. | Pavel Hrubes, Iddo Tzameret |
| 2012 | Solution of the propeller conjecture in R | Steven Heilman, Aukosh Jagannath, Assaf Naor |
| 2012 | Nearly optimal sparse fourier transform. | Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price |
| 2012 | Beating randomized response on incoherent matrices. | Moritz Hardt, Aaron Roth |
| 2012 | Folded codes from function field towers and improved optimal rate list decoding. | Venkatesan Guruswami, Chaoping Xing |
| 2012 | Reconstruction of depth-4 multilinear circuits with top fan-in 2. | Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam |
| 2012 | Structure theorem and isomorphism test for graphs with excluded topological subgraphs. | Martin Grohe, Dniel Marx |
| 2012 | Competitive contagion in networks. | Sanjeev Goyal, Michael J. Kearns |
| 2012 | Matroids and integrality gaps for hypergraphic steiner tree relaxations. | Michel X. Goemans, Neil Olver, Thomas Rothvo, Rico Zenklusen |
| 2012 | Polyhedral clinching auctions and the adwords polytope. | Gagan Goel, Vahab S. Mirrokni, Renato Paes Leme |
| 2012 | A tight RMR lower bound for randomized mutual exclusion. | George Giakkoupis, Philipp Woelfel |
| 2012 | A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities. | Jugal Garg, Ruta Mehta, Milind A. Sohoni, Vijay V. Vazirani |
| 2012 | Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. | Anna Gl, Kristoffer Arnsfelt Hansen, Michal Kouck, Pavel Pudlk, Emanuele Viola |