| 2012 | Multiparty Proximity Testing with Dishonest Majority from Equality Testing. | Ran Gelles, Rafail Ostrovsky, Kina Winoto |
| 2012 | Deciding First Order Properties of Matroids. | Tomas Gavenciak, Daniel Krl, Sang-il Oum |
| 2012 | Backdoors to Acyclic SAT. | Serge Gaspers, Stefan Szeider |
| 2012 | Self-assembly with Geometric Tiles. | Bin Fu, Matthew J. Patitz, Robert T. Schweller, Robert Sheline |
| 2012 | Computing Game Metrics on Markov Decision Processes. | Hongfei Fu |
| 2012 | Minimizing Rosenthal Potential in Multicast Games. | Fedor V. Fomin, Petr A. Golovach, Jesper Nederlof, Michal Pilipczuk |
| 2012 | Discrete Generalised Polynomial Functors - (Extended Abstract). | Marcelo P. Fiore |
| 2012 | Nominal Completion for Rewrite Systems with Binders. | Maribel Fernndez, Albert Rubio |
| 2012 | Parameterized Approximation via Fidelity Preserving Transformations. | Michael R. Fellows, Ariel Kulik, Frances A. Rosamond, Hadas Shachnai |
| 2012 | Universal Factor Graphs. | Uriel Feige, Shlomo Jozeph |
| 2012 | Time and Parallelizability Results for Parity Games with Bounded Treewidth. | John Fearnley, Sven Schewe |
| 2012 | Succinct Indices for Range Queries with Applications to Orthogonal Range Maxima. | Arash Farzan, J. Ian Munro, Rajeev Raman |
| 2012 | Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations. | Kousha Etessami, Alistair Stewart, Mihalis Yannakakis |
| 2012 | Space-Constrained Interval Selection. | Yuval Emek, Magns M. Halldrsson, Adi Rosn |
| 2012 | A QPTAS for ε-Envy-Free Profit-Maximizing Pricing on Line Graphs. | Khaled M. Elbassioni |
| 2012 | A Theory Independent Curry-De Bruijn-Howard Correspondence. | Gilles Dowek |
| 2012 | Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner. | Michael Dinitz, Guy Kortsarz, Ran Raz |
| 2012 | Deterministic Network Exploration by Anonymous Silent Agents with Local Traffic Reports. | Yoann Dieudonn, Andrzej Pelc |
| 2012 | Regular Languages Are Church-Rosser Congruential. | Volker Diekert, Manfred Kufleitner, Klaus Reinhardt, Tobias Walter |
| 2012 | Efficiency-Revenue Trade-Offs in Auctions. | Ilias Diakonikolas, Christos H. Papadimitriou, George Pierrakos, Yaron Singer |
| 2012 | Zero-One Rounding of Singular Vectors. | Amit Deshpande, Ravindran Kannan, Nikhil Srivastava |
| 2012 | The Inverse Shapley Value Problem. | Anindya De, Ilias Diakonikolas, Rocco A. Servedio |
| 2012 | Pebble Games with Algebraic Rules. | Anuj Dawar, Bjarki Holm |
| 2012 | Clique Cover and Graph Separation: New Incompressibility Results. | Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlstrm |
| 2012 | Max-Cut Parameterized above the Edwards-Erdős Bound. | Robert Crowston, Mark Jones, Matthias Mnich |