List of accepted papers for STACS 2012: 13/9-approximation for Graphic TSP Marcin Mucha. A (k + 3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems Justin Ward. A Pumping Lemma for Pushdown Graphs of Any Level Pawel Parys. Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth Michael Elberfeld, Andreas Jakoby and Till Tantau. An Approximation Algorithm for #k-SAT Marc Thurley. Asymptotic enumeration of Minimal Automata Frederique Bassino, Julien David and Andrea Sportiello. Balanced Partitions of Trees and Applications Andreas Emil Feldmann and Luca Foschini. Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property Gerth Stolting Brodal and Casper Kejlberg-Rasmussen. Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified Kai-Min Chung, Henry Lam, Zhenming Liu and Michael Mitzenmacher. Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P) Artur Jez. Concurrency Makes Simple Theories Hard Stefan Goller and Anthony Widjaja Lin. Conflict-free Chromatic Art Gallery Coverage Andreas Baertschi and Subhash Suri. Constant compression and random weights Wolfgang Merkle and Jason Teutsch. Contraction Checking in Graphs on Surfaces Marcin Kaminski and Dimitrios Thilikos. Distribution of the number of accessible states in a random deterministic automaton Arnaud Carayol and Cyril Nicaud. Edge-disjoint Odd Cycles in 4-edge-connected Graphs Ken-Ichi Kawarabayashi and Yusuke Kobayashi. Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P Volker Diekert, Jurn Laun and Alexander Ushakov. Efficiently Decodable Compressed Sensing by List-Recoverable Codes and Recursion Hung Ngo, Ely Porat and Atri Rudra. Ehrenfeucht-Fraisse goes elementarily automatic for structures of bounded degree Antoine Durand-Gasselin and Peter Habermehl. Improved bounds on Bipartite Matching on surfaces Samir Datta, Arjun Gopalan, Raghav Kulkarni and Raghunath Tewari. Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices Ioannis Koutis, Alex Levin and Richard Peng. Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid minor Ken-Ichi Kawarabayashi and Yusuke Kobayashi. Linear-Space Data Structures for Range Mode Query in Arrays Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison and Bryan T. Wilkinson. Log-supermodular functions, functional clones and counting CSPs Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg and Mark Jerrum. Low Randomness Rumor Spreading via Hashing George Giakkoupis, Thomas Sauerwald, He Sun and Philipp Woelfel. Lower bounds on the complexity of MSO1 model-checking Robert Ganian, Petr Hlineny, Alexander Langer, Jan Obdrzalek, Peter Rossmanith and Somnath Sikdar. LP can be a cure for Parameterized Problems Ramanujan M. S., Venkatesh Raman, Saket Saurabh and Narayanaswamy N. S.. Mind Change Speed-up for Learning Languages from Positive Data Sanjay Jain and Efim Kinber. Monomials in arithmetic circuits: Complete problems in the counting hierarchy Herve Fournier, Guillaume Malod and Stefan Mengel. Motion planning with pulley, rope, and baskets Christian Eggermont and Gerhard J. Woeginger. On Computing Pareto Stable Assignments Ning Chen. On separation question for tree languages Andre Arnold, Henryk Michalewski and Damian Niwinski. On treewidth and related parameters of random geometric graphs Dieter Mitsche and Guillem Perarnau. Optimizing Linear Functions with Randomized Search Heuristics -- The Robustness of Mutation Carsten Witt. Parameterized Complexity of Connected Even/Odd Subgraph Problems Fedor V. Fomin and Petr Golovach. Playing Mastermind With Constant-Size Memory Benjamin Doerr and Carola Winzen. Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers Laszlo Babai and Youming Qiao. Preemptive and Non-Preemptive Generalized Min Sum Set Cover Sungjin Im, Maxim Sviridenko and Ruben Van Der Zwaan. Randomized Communication Complexity for Linear Algebra Problems over Finite Fields Xiaoming Sun and Chengu Wang. Regular tree languages, cardinality predicates, and addition-invariant FO Frederik Harwath and Nicole Schweikardt. Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem Khaled Elbassioni, Katarzyna Paluch and Anke Van Zuylen. Stabilization of Branching Queueing Networks Tomas Brazdil and Stefan Kiefer. Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes Maurice Jansen and Rahul Santhanam. Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces Paul Bonsma. The Determinacy of Context-Free Games Olivier Finkel. The Denjoy alternative for computable functions Laurent Bienvenu, Rupert Holzl, Joseph Miller and Andre Nies. The dimension of ergodic random sequences Mathieu Hoyrup. The Field of Reals is not omega-Automatic Faried Abu Zaid, Erich Gradel and Lukasz Kaiser. The Limits of Decidability for First-Order Logic on CPDA Graphs Christopher Broadbent. The Power of Local Search: Maximum Coverage over a Matroid Yuval Filmus and Justin Ward. Trichotomy for Integer Linear Systems Based on Their Sign Patterns Kei Kimura and Kazuhisa Makino. Tying up the loose ends in fully LZW-compressed pattern matching Pawel Gawrychowski. Variable time amplitude amplification and quantum algorithms for linear algebra problems Andris Ambainis. Weak MSO+U over infinite trees Mikolaj Bojanczyk and Szymon Torunczyk.