| 2012 | Interactive information complexity. | Mark Braverman |
| 2012 | An analysis of one-dimensional schelling segregation. | Christina Brandt, Nicole Immorlica, Gautam Kamath, Robert Kleinberg |
| 2012 | Multiparty computation secure against continual memory leakage. | Elette Boyle, Shafi Goldwasser, Abhishek Jain, Yael Tauman Kalai |
| 2012 | Monotone expansion. | Jean Bourgain, Amir Yehudayoff |
| 2012 | Unconditional differentially private mechanisms for linear queries. | Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, Kunal Talwar |
| 2012 | Span programs for functions with constant-sized 1-certificates: extended abstract. | Aleksandrs Belovs |
| 2012 | Budget feasible mechanism design: from prior-free to bayesian. | Xiaohui Bei, Ning Chen, Nick Gravin, Pinyan Lu |
| 2012 | Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. | Paul Beame, Christopher Beck, Russell Impagliazzo |
| 2012 | Robust satisfiability of constraint satisfaction problems. | Libor Barto, Marcin Kozik |
| 2012 | The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. | Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer |
| 2012 | Hypercontractivity, sum-of-squares proofs, and their applications. | Boaz Barak, Fernando G. S. L. Brando, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou |
| 2012 | Tight time-space tradeoff for mutual exclusion. | Nikhil Bansal, Vibhor Bhatt, Prasad Jayanti, Ranganath Kondapally |
| 2012 | Rational proofs. | Pablo Daniel Azar, Silvio Micali |
| 2012 | Computing a nonnegative matrix factorization - provably. | Sanjeev Arora, Rong Ge, Ravindran Kannan, Ankur Moitra |
| 2012 | Pseudorandom generators with long stretch and low locality from random local one-way functions. | Benny Applebaum |
| 2012 | Improving christofides' algorithm for the s-t path TSP. | Hyung-Chan An, Robert Kleinberg, David B. Shmoys |
| 2012 | Nearly complete graphs decomposable into large induced matchings and their applications. | Noga Alon, Ankur Moitra, Benny Sudakov |
| 2012 | Determinism versus nondeterminism with arithmetic tests and computation: extended abstract. | Mikls Ajtai |
| 2012 | Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits. | Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena |
| 2012 | Optimal online buffer scheduling for block devices. | Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Rcke |
| 2012 | Using petal-decompositions to build a low stretch spanning tree. | Ittai Abraham, Ofer Neiman |
| 2012 | Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. | Ittai Abraham, Shiri Chechik, Cyril Gavoille |
| 2012 | Minimax option pricing meets black-scholes in the limit. | Jacob D. Abernethy, Rafael M. Frongillo, Andre Wibisono |
| 2012 | Quantum money from hidden subspaces. | Scott Aaronson, Paul F. Christiano |
| 2011 | From affine to two-source extractors via approximate duality. | Noga Zewi, Eli Ben-Sasson |