| 2012 | A Characterization of Bispecial Sturmian Words. Gabriele Fici |
| 2012 | A Dichotomy Theorem for Homomorphism Polynomials. Nicolas de Rugy-Altherre |
| 2012 | A Finite Basis for 'Almost Future' Temporal Logic over the Reals. Dorit Pardo Ordentlich, Alexander Rabinovich |
| 2012 | A Polynomial-Time Algorithm for Computing the Maximum Common Subgraph of Outerplanar Graphs of Bounded Degree. Tatsuya Akutsu, Takeyuki Tamura |
| 2012 | A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments. Mingyu Xiao, Jiong Guo |
| 2012 | A Toolkit for Proving Limitations of the Expressive Power of Logics. Nicole Schweikardt |
| 2012 | Abelian Pattern Avoidance in Partial Words. Francine Blanchet-Sadri, Sean Simmons |
| 2012 | An Improved Approximation Scheme for Variable-Sized Bin Packing. Klaus Jansen, Stefan Erich Julius Kraft |
| 2012 | Approximate Graph Isomorphism. Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Yadu Vasudev |
| 2012 | Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games. Matús Mihalák, Jan Christoph Schlegel |
| 2012 | Between Tree Patterns and Conjunctive Queries: Is There Tractability beyond Acyclicity? Filip Murlak, Michal Oginski, Marcin Przybylko |
| 2012 | Categories of Coalgebraic Games. Furio Honsell, Marina Lenisa, Rekha Redamalla |
| 2012 | Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width. Martin Doucha, Jan Kratochvíl |
| 2012 | Coloring Graphs Characterized by a Forbidden Subgraph. Petr A. Golovach, Daniël Paulusma, Bernard Ries |
| 2012 | Computation of Least Fixed Points. Mihalis Yannakakis |
| 2012 | Computational Aspects of Cellular Automata on Countable Sofic Shifts. Ville Salo, Ilkka Törmä |
| 2012 | Computational Complexity of Smooth Differential Equations. Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick, Martin Ziegler |
| 2012 | Computing Lempel-Ziv Factorization Online. Tatiana Starikovskaya |
| 2012 | Computing with Large Populations Using Interactions. Olivier Bournez, Pierre Fraigniaud, Xavier Koegler |
| 2012 | Constructing Premaximal Ternary Square-Free Words of Any Level. Elena A. Petrova, Arseny M. Shur |
| 2012 | Descriptional Complexity of Deterministic Regular Expressions. Katja Losemann, Wim Martens, Matthias Niewerth |
| 2012 | Drawing Planar Graphs on Points Inside a Polygon. Therese Biedl, Peter Floderus |
| 2012 | Equations X + A = B and (X + X) + C = (X - X) + D over Sets of Natural Numbers. Tommi Lehtinen |
| 2012 | Fast Balanced Partitioning Is Hard Even on Grids and Trees. Andreas Emil Feldmann |
| 2012 | Fine and Wilf's Theorem and Pseudo-repetitions. Florin Manea, Robert Mercas, Dirk Nowotka |
| 2012 | Finite State Transducers for Modular Möbius Number Systems. Martin Delacourt, Petr Kurka |
| 2012 | Gathering an Even Number of Robots in an Odd Ring without Global Multiplicity Detection. Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil |
| 2012 | Generating Functions of Timed Languages. Eugene Asarin, Nicolas Basset, Aldric Degorre, Dominique Perrin |
| 2012 | How to Reconstruct a Genome. Esko Ukkonen |
| 2012 | Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs. Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah |
| 2012 | In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses. Jingsen Chen, Stefan Edelkamp, Amr Elmasry, Jyrki Katajainen |
| 2012 | Kernels for Edge Dominating Set: Simpler or Smaller. Torben Hagerup |
| 2012 | Light Spanners in Bounded Pathwidth Graphs. Michelangelo Grigni, Hao-Hsiang Hung |
| 2012 | Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings Branislav Rovan, Vladimiro Sassone, Peter Widmayer |
| 2012 | Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs. Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis |
| 2012 | Model Checking Stochastic Branching Processes. Taolue Chen, Klaus Dräger, Stefan Kiefer |
| 2012 | Mortality for 2×2 Matrices Is NP-Hard. Paul C. Bell, Mika Hirvensalo, Igor Potapov |
| 2012 | Near-Optimal Expanding Generator Sets for Solvable Permutation Groups. Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev |
| 2012 | New Advances in Reoptimizing the Minimum Steiner Tree Problem. Davide Bilò, Anna Zych |
| 2012 | New Races in Parameterized Algorithmics. Christian Komusiewicz, Rolf Niedermeier |
| 2012 | Observe and Remain Silent (Communication-Less Agent Location Discovery). Tom Friedetzky, Leszek Gasieniec, Thomas Gorry, Russell Martin |
| 2012 | Obtaining Planarity by Contracting Few Edges. Petr A. Golovach, Pim van 't Hof, Daniël Paulusma |
| 2012 | On Two Stronger Versions of Dejean's Conjecture. Igor N. Tunev, Arseny M. Shur |
| 2012 | On the Complexity of Ontological Reasoning under Disjunctive Existential Rules. Georg Gottlob, Marco Manna, Michael Morak, Andreas Pieris |
| 2012 | On the Impact of Fair Best Response Dynamics. Angelo Fanelli, Luca Moscardelli, Alexander Skopalik |
| 2012 | Online Sum-Radii Clustering. Dimitris Fotakis, Paraschos Koutris |
| 2012 | Pancake Flipping Is Hard. Laurent Bulteau, Guillaume Fertin, Irena Rusu |
| 2012 | Parameterized Study of the Test Cover Problem. Robert Crowston, Gregory Z. Gutin, Mark Jones, Saket Saurabh, Anders Yeo |
| 2012 | Planarizing Gadgets for Perfect Matching Do Not Exist. Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf |
| 2012 | Probabilistic Automata and Probabilistic Logic. Thomas Weidner |
| 2012 | Quasi-recognizable vs MSO Definable Languages of One-Dimensional Overlapping Tiles - (Extended Abstract). David Janin |
| 2012 | Reducing a Target Interval to a Few Exact Queries. Jesper Nederlof, Erik Jan van Leeuwen, Ruben van der Zwaan |
| 2012 | Reductions to the Set of Random Strings: The Resource-Bounded Case. Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff |
| 2012 | Regularity Problems for Weak Pushdown ω-Automata and Games. Christof Löding, Stefan Repke |
| 2012 | Reversal Hierarchies for Small 2DFAs. Christos A. Kapoutsis, Giovanni Pighizzini |
| 2012 | Scott Is Always Simple. Antonino Salibra |
| 2012 | Simple Models for Recursive Schemes. Igor Walukiewicz |
| 2012 | Sitting Closer to Friends Than Enemies, Revisited. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk |
| 2012 | Smoothed Complexity Theory. Markus Bläser, Bodo Manthey |
| 2012 | Solving Counter Parity Games. Dietmar Berwanger, Lukasz Kaiser, Simon Leßenich |
| 2012 | Strategy Machines and Their Complexity. Marcus Gelderie |
| 2012 | Strictness of the Collapsible Pushdown Hierarchy. Alexander Kartzow, Pawel Parys |
| 2012 | Taking It to the Limit: Approximate Reasoning for Markov Processes. Kim Guldstrand Larsen, Radu Mardare, Prakash Panangaden |
| 2012 | The Complexity of Rerouting Shortest Paths. Paul S. Bonsma |
| 2012 | The Join Levels of the Trotter-Weil Hierarchy Are Decidable. Manfred Kufleitner, Alexander Lauser |
| 2012 | The Lower Reaches of Circuit Uniformity. Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie |
| 2012 | The Robust Set Problem: Parameterized Complexity and Approximation. Cristina Bazgan, Morgan Chopin |
| 2012 | Transportation under Nasty Side Constraints. Gerhard J. Woeginger |
| 2012 | Unordered Constraint Satisfaction Games. Lauri Ahlroth, Pekka Orponen |
| 2012 | Weakly-Synchronized Ground Tree Rewriting - (with Applications to Verifying Multithreaded Programs). Anthony Widjaja Lin |
| 2012 | When Trees Grow Low: Shrubs and Fast MSO1. Robert Ganian, Petr Hlinený, Jaroslav Nesetril, Jan Obdrzálek, Patrice Ossona de Mendez, Reshma Ramadurai |
| 2012 | Zero-Knowledge Proofs via Polynomial Representations. Giovanni Di Crescenzo, Vadym Fedyukovych |