| 2012 | On identity testing of tensors, low-rank recovery and compressed sensing. | Michael A. Forbes, Amir Shpilka |
| 2012 | Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. | Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf |
| 2012 | Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars. | Kousha Etessami, Alistair Stewart, Mihalis Yannakakis |
| 2012 | From irreducible representations to locally decodable codes. | Klim Efremenko |
| 2012 | Separating multilinear branching programs and formulas. | Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff |
| 2012 | Subspace evasive sets. | Zeev Dvir, Shachar Lovett |
| 2012 | From query complexity to computational complexity. | Shahar Dobzinski, Jan Vondrk |
| 2012 | Online matching with concave returns. | Nikhil R. Devanur, Kamal Jain |
| 2012 | Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces. | Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio |
| 2012 | Learning poisson binomial distributions. | Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio |
| 2012 | Catching the k-NAESAT threshold. | Amin Coja-Oghlan, Konstantinos Panagiotou |
| 2012 | Routing in undirected graphs with constant congestion. | Julia Chuzhoy |
| 2012 | On vertex sparsifiers with Steiner nodes. | Julia Chuzhoy |
| 2012 | Fast matrix rank algorithms and applications. | Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau |
| 2012 | On the limits of black-box reductions in mechanism design. | Shuchi Chawla, Nicole Immorlica, Brendan Lucier |
| 2012 | Tight bounds for monotone switching networks via fourier analysis. | Siu Man Chan, Aaron Potechin |
| 2012 | Approximation algorithms and hardness of integral concurrent flow. | Parinya Chalermsook, Julia Chuzhoy, Alina Ene, Shi Li |
| 2012 | When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks. | Amit Chakrabarti, Lisa Fleischer, Christophe Weibel |
| 2012 | Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. | Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov |
| 2012 | Finding red balloons with split contracts: robustness to individuals' selfishness. | Manuel Cebrin, Lorenzo Coviello, Andrea Vattani, Panagiotis Voulgaris |
| 2012 | An algorithmic characterization of multi-dimensional mechanisms. | Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg |
| 2012 | Complexity of counting CSP with complex weights. | Jin-Yi Cai, Xi Chen |
| 2012 | Tight lower bounds for the online labeling problem. | Jan Bulnek, Michal Kouck, Michael E. Saks |
| 2012 | Improved smoothed analysis of multiobjective optimization. | Tobias Brunsch, Heiko Rglin |
| 2012 | Strict fibonacci heaps. | Gerth Stlting Brodal, George Lagogiannis, Robert Endre Tarjan |