The program committee of STACS 2006 selected 54 out of 283 submissions, sorted here by submission number.

20. Vince Barany, Christof Loeding and Olivier Serre. Regularity Problems for Visibly Pushdown Languages.
25. Dalia Krieger. On Critical Exponents in Fixed Points of Binary $k$-Uniform Morphisms.
28. Joost Engelfriet and Hendrik Jan Hoogeboom. Nested Pebbles and Transitive Closure.
29. Georg Schnitger. Regular expressions and NFAs without epsilon-transitions.
31. Krishnendu Chatterjee, Rupak Majumdar and Thomas A. Henzinger. Markov Decision Processes with  Multiple Objectives.
40. Reuven Cohen and David Peleg. Convergence of Autonomous Mobile Robots With Inaccurate Sensors and Movements.
52. Christian Glaßer, Aduri Pavan, Alan L. Selman and Liyu Zhang. Redundancy in Complete Sets.
57. Krishnendu Chatterjee and Thomas A. Henzinger. Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games.
61. Nutan Limaye, Meena Mahajan and Jayalal Sarma M N. Evaluating Monotone Circuits on Cylinders, Planes and Torii.
65. Lance Fortnow, Troy Lee and Nikolai Vereshchagin. Kolmogorov complexity with error.
73. Stephanie Wehner. Entanglement in Interactive Proof Systems with Binary Answers.
74. Susanne Albers and Hiroshi Fujiwara. Energy-Efficient Algorithms for Flow Time Minimization.
76. Vinayaka Pandit and Rohit Khandekar. Online Sorting Buffers on Line.
80. Rasmus Pagh, Anna Pagh and Rolf Fagerberg. External String Sorting: Faster and Cache-Oblivious.
85. Iwona Bialynicka-Birula and Roberto Grossi. Amortized Rigidness in Dynamic Cartesian Trees.
88. Vince Barany. Invariants of automatic presentations and semi-synchronous transductions.
95. Daniel Mölle, Stefan Richter and Peter Rossmanith. A Faster Algorithm for the Steiner Tree Problem.
99. Bjoern Kjos-Hanssen, Wolfgang Merkle and Frank Stephan. Kolmogorov complexity and the recursion theorem.
103. Yossi Azar and Yoel Chaiutin. Optimal Node Routing.
104. Manindra Agrawal and Nitin Saxena. Equivalence of F-algebras and cubic forms.
110. Alexander Healy and Emanuele Viola. Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two.
119. Dimitris Fotakis. Memoryless Facility Location in One Pass.
120. Khaled Elbassioni and Nabil Mustafa. Conflict-Free Colorings of Rectangle Ranges.
125. Benjamin Doerr. Generating Randomized Roundings with Cardinality Constraints and Derandomizations.
142. Josep Diaz and Dimitrios Thilikos. Fast FPT-algorithms for cleaning grids.
143. Dietrich Kuske. Weighted asynchronous cellular automata.
144. Sebastian Aland, Dominic Dumrauf, Martin Gairing, Burkhard Monien and Florian Schoppmann. Exact Price of Anarchy for Polynomial Congestion Games.
148. Amitabha Roy and Howard Straubing. Definability of Languages by Generalized First-Order Formulas over (N,+).
150. Andris Ambainis and Robert Spalek. Quantum Algorithms for Matching and Network Flows.
151. Harry Buhrman, Leen Torenvliet and Falk Unger. Sparse selfreducible sets and polynomial size circuit lower bounds.
152. Olivier Finkel. On the Accepting Power of  $2$-Tape B\"uchi Automata.
165. Venkatesan Chakaravarthy and Sambuddha Roy. Oblivious Symmetric Alternation.
166. Ahmed Belal and Amr Elmasry. Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes.
193. Wojciech Rytter. The Number of Runs in a String: Improved  Analysis of of the Linear Upper Bound.
204. Tzur Sayag, Shai Fine and Yishay Mansour. Combining Multiple Heuristics.
208. Mirela Damian, Robin Flatland and Joseph O'Rourke. Grid Vertex-Unfolding Orthogonal Polyhedra.
212. Marie-Pierre Béal and Dominique Perrin. Complete codes in a sofic shift.
214. Bin Fu. Theory and Application of Width Bounded Geometric Separator.
215. Dietmar Berwanger, Anuj Dawar, Paul Hunter and Stephan Kreutzer. DAG-Width and Parity Games.
216. Maxim Ushakov and Andrey Rumyantsev. Forbidden substrings, Kolmogorov complexity and almost periodic sequences.
220. Andrei Romashchenko. Reliable Computations Based on Locally Decodable Codes.
223. Kousha Etessami and Mihalis Yannakakis. Efficient Analysis of Classes of Recursive Markov Decision Processes and Stochastic Games.
225. Chinmoy Dutta and Jaikumar Radhakrishnan. Tradeoffs in depth-two superconcentrators.
226. Ina Maeurer. Weighted Picture Automata and Weighted Logics.
235. Paolo Penna and Carmine Ventre. The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms.
237. John Hitchcock. Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets.
241. Michael Bauland, Edith Hemaspaandra, Ilka Johannsen and Henning Schnoor. Generalized Modal Satisfiability.
252. Manuel Bodirsky and Victor Dalmau. Datalog and Constraint Satisfaction with Infinite Templates.
255. Darin Goldstein and Kojiro Kobayashi. On the Complexity of the "Most General" Firing Squad Synchronization Problem.
264. George Christodoulou, Vahab Mirrokni and Anastasios Sidiropoulos. Convergence and Approximation in Potential Games.
266. Adam Klivans and Lance Fortnow. Linear Advice for Randomized Logarithmic Space.
267. Vikraman Arvind and Johannes Koebler. On Hypergraph and Graph Isomorphism with Bounded Color Classes.
273. Amit Chakrabarti, Khanh Do Ba and S. Muthukrishnan. Estimating Entropy and Entropy Norm on Data Streams.
283. Daniel Golovin, Vineet Goyal and R. Ravi. Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems.