23. STACS 2006: Marseille, France

• Philippe Flajolet:
  The Ubiquitous Digital Tree. 1-22
  
• Gene Itkis, Leonid A. Levin:
  Flat Holonomies on Automata Networks. 23-49
  
• Markus Müller-Olm, Michael Petter, Helmut Seidl:
  Interprocedurally Analyzing Polynomial Identities. 50-67
  
• Rolf Fagerberg, Anna Pagh, Rasmus Pagh:
  External String Sorting: Faster and Cache-Oblivious. 68-79
  
• Iwona Bialynicka-Birula, Roberto Grossi:
  Amortized Rigidness in Dynamic Cartesian Trees. 80-91
  
• Ahmed A. Belal, Amr Elmasry:
  Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes. 92-103
  
• Dalia Krieger:
  On Critical Exponents in Fixed Points of Binary k-Uniform Morphisms. 104-114
  
• Manindra Agrawal, Nitin Saxena:
  Equivalence of F-Algebras and Cubic Forms. 115-126
  
• Marie-Pierre Béal, Dominique Perrin:
  Complete Codes in a Sofic Shift. 127-136
  
• Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin:
  Kolmogorov Complexity with Error. 137-148
  
• Bjørn Kjos-Hanssen, Wolfgang Merkle, Frank Stephan:
  Kolmogorov Complexity and the Recursion Theorem. 149-161
  
• Stephanie Wehner:
  Entanglement in Interactive Proof Systems with Binary Answers. 162-171
  
• Andris Ambainis, Robert Spalek:
  Quantum Algorithms for Matching and Network Flows. 172-183
  
• Wojciech Rytter:
  The Number of Runs in a String: Improved Analysis of the Linear Upper Bound. 184-195
  
• Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan:
  Estimating Entropy and Entropy Norm on Data Streams. 196-205
  
• Daniel Golovin, Vineet Goyal, R. Ravi:
  Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems. 206-217
  
• Sebastian Aland, Dominic Dumrauf, Martin Gairing, Burkhard Monien, Florian Schoppmann:
  Exact Price of Anarchy for Polynomial Congestion Games. 218-229
  
• Venkatesan T. Chakaravarthy, Sambuddha Roy:
  Oblivious Symmetric Alternation. 230-241
  
• Tzur Sayag, Shai Fine, Yishay Mansour:
  Combining Multiple Heuristics. 242-253
  
• Khaled M. Elbassioni, Nabil H. Mustafa:
  Conflict-Free Colorings of Rectangles Ranges. 254-263
  
• Mirela Damian, Robin Y. Flatland, Joseph O'Rourke:
  Grid Vertex-Unfolding Orthogonal Polyhedra. 264-276
  
• Bin Fu:
  Theory and Application of Width Bounded Geometric Separator. 277-288
  
• Vince Bárány:
  Invariants of Automatic Presentations and Semi-synchronous Transductions. 289-300
  
• Olivier Finkel:
  On the Accepting Power of 2-Tape Büchi Automata. 301-312
  
• Ina Mäurer:
  Weighted Picture Automata and Weighted Logics. 313-324
  
• Krishnendu Chatterjee, Rupak Majumdar, Thomas A. Henzinger:
  Markov Decision Processes with Multiple Objectives. 325-336
  
• Paolo Penna, Carmine Ventre:
  The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms. 337-348
  
• George Christodoulou, Vahab S. Mirrokni, Anastasios Sidiropoulos:
  Convergence and Approximation in Potential Games. 349-360
  
• Josep Díaz, Dimitrios M. Thilikos:
  Fast FPT-Algorithms for Cleaning Grids. 361-371
  
• Chinmoy Dutta, Jaikumar Radhakrishnan:
  Tradeoffs in Depth-Two Superconcentrators. 372-383
  
• Vikraman Arvind, Johannes Köbler:
  On Hypergraph and Graph Isomorphism with Bounded Color Classes. 384-395
  
• Andrey Yu. Rumyantsev, M. A. Ushakov:
  Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences. 396-407
  
• John M. Hitchcock:
  Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. 408-419
  
• Vince Bárány, Christof Löding, Olivier Serre:
  Regularity Problems for Visibly Pushdown Languages. 420-431
  
• Georg Schnitger:
  Regular Expressions and NFAs Without epsilon-Transitions. 432-443
  
• Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang:
  Redundancy in Complete Sets. 444-454
  
• Harry Buhrman, Leen Torenvliet, Falk Unger:
  Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds. 455-468
  
• Lance Fortnow, Adam R. Klivans:
  Linear Advice for Randomized Logarithmic Space. 469-476
  
• Joost Engelfriet, Hendrik Jan Hoogeboom:
  Nested Pebbles and Transitive Closure. 477-488
  
• Amitabha Roy, Howard Straubing:
  Definability of Languages by Generalized First-Order Formulas over (N, +). 489-499
  
• Michael Bauland, Edith Hemaspaandra, Henning Schnoor, Ilka Schnoor:
  Generalized Modal Satisfiability. 500-511
  
• Krishnendu Chatterjee, Thomas A. Henzinger:
  Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games. 512-523
  
• Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer:
  DAG-Width and Parity Games. 524-536
  
• Andrei E. Romashchenko:
  Reliable Computations Based on Locally Decodable Codes. 537-548
  
• Reuven Cohen, David Peleg:
  Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements. 549-560
  
• Daniel Mölle, Stefan Richter, Peter Rossmanith:
  A Faster Algorithm for the Steiner Tree Problem. 561-570
  
• Benjamin Doerr:
  Generating Randomized Roundings with Cardinality Constraints and Derandomizations. 571-583
  
• Rohit Khandekar, Vinayaka Pandit:
  Online Sorting Buffers on Line. 584-595
  
• Yossi Azar, Yoel Chaiutin:
  Optimal Node Routing. 596-607
  
• Dimitris Fotakis:
  Memoryless Facility Location in One Pass. 608-620
  
• Susanne Albers, Hiroshi Fujiwara:
  Energy-Efficient Algorithms for Flow Time Minimization. 621-633
  
• Kousha Etessami, Mihalis Yannakakis:
  Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games. 634-645
  
• Manuel Bodirsky, Víctor Dalmau:
  Datalog and Constraint Satisfaction with Infinite Templates. 646-659
  
• Nutan Limaye, Meena Mahajan, Jayalal M. N. Sarma:
  Evaluating Monotone Circuits on Cylinders, Planes and Tori. 660-671
  
• Alexander Healy, Emanuele Viola:
  Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two. 672-683
  
• Dietrich Kuske:
  Weighted Asynchronous Cellular Automata. 684-695
  
• Darin Goldstein, Kojiro Kobayashi:
  On the Complexity of the "Most General" Firing Squad Synchronization Problem. 696-711