| 2012 | Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. | Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Saket Saurabh |
| 2012 | A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint. | Yuval Filmus, Justin Ward |
| 2012 | The Privacy of the Analyst and the Power of the State. | Cynthia Dwork, Moni Naor, Salil P. Vadhan |
| 2012 | New Limits to Classical and Quantum Instance Compression. | Andrew Drucker |
| 2012 | The Tile Assembly Model is Intrinsically Universal. | David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Damien Woods |
| 2012 | LP Rounding for k-Centers with Non-uniform Hard Capacities. | Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller |
| 2012 | Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings. | Marek Cygan, Harold N. Gabow, Piotr Sankowski |
| 2012 | A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2. | Julia Chuzhoy, Shi Li |
| 2012 | Computing Multiplicities of Lie Group Representations. | Matthias Christandl, Brent Doran, Michael Walter |
| 2012 | Everywhere-Sparse Spanners via Dense Subgraphs. | Eden Chlamtac, Michael Dinitz, Robert Krauthgamer |
| 2012 | Designing FPT Algorithms for Cut Problems Using Randomized Contractions. | Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk |
| 2012 | The Dynamics of Influence Systems. | Bernard Chazelle |
| 2012 | Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. | Arkadev Chattopadhyay, Rahul Santhanam |
| 2012 | The Cutting Plane Method Is Polynomial for Perfect Matchings. | Karthekeyan Chandrasekaran, Lszl A. Vgh, Santosh S. Vempala |
| 2012 | Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization. | Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg |
| 2012 | Split and Join: Strong Partitions and Universal Steiner Trees for Graphs. | Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman, Srinivasagopalan Srivathsan |
| 2012 | A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization. | Niv Buchbinder, Moran Feldman, Joseph Naor, Roy Schwartz |
| 2012 | Approximation Limits of Linear Programs (Beyond Hierarchies). | Gbor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer |
| 2012 | Efficient Interactive Coding against Adversarial Noise. | Zvika Brakerski, Yael Tauman Kalai |
| 2012 | The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy. | Jeremiah Blocki, Avrim Blum, Anupam Datta, Or Sheffet |
| 2012 | Partially Symmetric Functions Are Efficiently Isomorphism-Testable. | Eric Blais, Amit Weinstein, Yuichi Yoshida |
| 2012 | From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique. | Nir Bitansky, Omer Paneth |
| 2012 | On the Complexity of Finding Narrow Proofs. | Christoph Berkholz |
| 2012 | Quasi-optimal Multiplication of Linear Differential Operators. | Alexandre Benot, Alin Bostan, Joris van der Hoeven |
| 2012 | Sparse Affine-Invariant Linear Codes Are Locally Testable. | Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan |