| 2012 | Fine and Wilf's Theorem and Pseudo-repetitions. | Florin Manea, Robert Mercas, Dirk Nowotka |
| 2012 | Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs. | Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah |
| 2012 | Descriptional Complexity of Deterministic Regular Expressions. | Katja Losemann, Wim Martens, Matthias Niewerth |
| 2012 | Regularity Problems for Weak Pushdown ω-Automata and Games. | Christof Lding, Stefan Repke |
| 2012 | Weakly-Synchronized Ground Tree Rewriting - (with Applications to Verifying Multithreaded Programs). | Anthony Widjaja Lin |
| 2012 | Equations X + A = B and (X + X) + C = (X - X) + D over Sets of Natural Numbers. | Tommi Lehtinen |
| 2012 | Taking It to the Limit: Approximate Reasoning for Markov Processes. | Kim Guldstrand Larsen, Radu Mardare, Prakash Panangaden |
| 2012 | The Join Levels of the Trotter-Weil Hierarchy Are Decidable. | Manfred Kufleitner, Alexander Lauser |
| 2012 | New Races in Parameterized Algorithmics. | Christian Komusiewicz, Rolf Niedermeier |
| 2012 | Computational Complexity of Smooth Differential Equations. | Akitoshi Kawamura, Hiroyuki Ota, Carsten Rsnick, Martin Ziegler |
| 2012 | Strictness of the Collapsible Pushdown Hierarchy. | Alexander Kartzow, Pawel Parys |
| 2012 | Reversal Hierarchies for Small 2DFAs. | Christos A. Kapoutsis, Giovanni Pighizzini |
| 2012 | Gathering an Even Number of Robots in an Odd Ring without Global Multiplicity Detection. | Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sbastien Tixeuil |
| 2012 | An Improved Approximation Scheme for Variable-Sized Bin Packing. | Klaus Jansen, Stefan Erich Julius Kraft |
| 2012 | Quasi-recognizable vs MSO Definable Languages of One-Dimensional Overlapping Tiles - (Extended Abstract). | David Janin |
| 2012 | Categories of Coalgebraic Games. | Furio Honsell, Marina Lenisa, Rekha Redamalla |
| 2012 | Kernels for Edge Dominating Set: Simpler or Smaller. | Torben Hagerup |
| 2012 | Planarizing Gadgets for Perfect Matching Do Not Exist. | Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf |
| 2012 | Light Spanners in Bounded Pathwidth Graphs. | Michelangelo Grigni, Hao-Hsiang Hung |
| 2012 | On the Complexity of Ontological Reasoning under Disjunctive Existential Rules. | Georg Gottlob, Marco Manna, Michael Morak, Andreas Pieris |
| 2012 | Coloring Graphs Characterized by a Forbidden Subgraph. | Petr A. Golovach, Danil Paulusma, Bernard Ries |
| 2012 | Obtaining Planarity by Contracting Few Edges. | Petr A. Golovach, Pim van 't Hof, Danil Paulusma |
| 2012 | Strategy Machines and Their Complexity. | Marcus Gelderie |
| 2012 | When Trees Grow Low: Shrubs and Fast MSO1. | Robert Ganian, Petr Hlinen, Jaroslav Nesetril, Jan Obdrzlek, Patrice Ossona de Mendez, Reshma Ramadurai |
| 2012 | Observe and Remain Silent (Communication-Less Agent Location Discovery). | Tom Friedetzky, Leszek Gasieniec, Thomas Gorry, Russell Martin |