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