| 2012 | Single Source - All Sinks Max Flows in Planar Digraphs. | Jakub Lacki, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen |
| 2012 | Representative Sets and Irrelevant Vertices: New Tools for Kernelization. | Stefan Kratsch, Magnus Wahlstrm |
| 2012 | On-Line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List. | Tsvi Kopelowitz |
| 2012 | Hardness of Finding Independent Sets in Almost q-Colorable Graphs. | Subhash Khot, Rishi Saket |
| 2012 | Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications. | Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jrmie Roland, David Xiao |
| 2012 | Combinatorial Coloring of 3-Colorable Graphs. | Ken-ichi Kawarabayashi, Mikkel Thorup |
| 2012 | A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions. | Daniel M. Kane |
| 2012 | Formulas Resilient to Short-Circuit Errors. | Yael Tauman Kalai, Allison B. Lewko, Anup Rao |
| 2012 | A Direct Product Theorem for the Two-Party Bounded-Round Public-Coin Communication Complexity. | Rahul Jain, Attila Pereszlnyi, Penghui Yao |
| 2012 | A New Direction for Counting Perfect Matchings. | Taisuke Izumi, Tadashi Wadayama |
| 2012 | A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers. | Tsuyoshi Ito, Thomas Vidick |
| 2012 | Pseudorandomness from Shrinkage. | Russell Impagliazzo, Raghu Meka, David Zuckerman |
| 2012 | The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal. | Zhiyi Huang, Sampath Kannan |
| 2012 | Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls. | Thomas Holenstein, Makrand Sinha |
| 2012 | Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space. | Sariel Har-Peled, Nirman Kumar |
| 2012 | Faster SDP Hierarchy Solvers for Local Rounding Algorithms. | Venkatesan Guruswami, Ali Kemal Sinop |
| 2012 | Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths. | Fabrizio Grandoni, Virginia Vassilevska Williams |
| 2012 | Constructing Non-malleable Commitments: A Black-Box Approach. | Vipul Goyal, Chen-Kuei Lee, Rafail Ostrovsky, Ivan Visconti |
| 2012 | Positive Results for Concurrently Secure Computation in the Plain Model. | Vipul Goyal |
| 2012 | Better Pseudorandom Generators from Milder Pseudorandom Restrictions. | Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan |
| 2012 | How to Compute in the Presence of Leakage. | Shafi Goldwasser, Guy N. Rothblum |
| 2012 | Matching with Our Eyes Closed. | Gagan Goel, Pushkar Tripathi |
| 2012 | Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. | Shayan Oveis Gharan, Luca Trevisan |
| 2012 | Faster Algorithms for Rectangular Matrix Multiplication. | Franois Le Gall |
| 2012 | Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design. | Takuro Fukunaga, R. Ravi |