2006 Marseille
Welcome ~ Important dates ~ Invited speakers ~ Program committee ~ Previous STACS ~ Call for papers ~ Submission ~ Accepted papers ~ Registration ~ Program ~ Organizing committee ~ Accomodations ~ Travel information ~ Sponsors ~ Contact


Thursday February 23, 2006

09:00 Opening and Plenary Session: Invited Talk Philippe FlajoletThe Ubiquitous Digital Tree Chair: Bruno Durand
10:10Coffee break
10:40 Session 1A Chair: Peter Sanders Session 1B Chair: Jean-Eric Pin
Rasmus Pagh, Anna Pagh and Rolf Fagerberg.External String Sorting: Faster and Cache-Oblivious.Dalia Krieger.On Critical Exponents in Fixed Points of Binary $k$-Uniform Morphisms.
Iwona Bialynicka-Birula and Roberto Grossi.Amortized Rigidness in Dynamic Cartesian Trees.Manindra Agrawal and Nitin Saxena.Equivalence of F-algebras and cubic forms.
Ahmed Belal and Amr Elmasry.Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes.Marie-Pierre Béal and Dominique Perrin.Complete codes in a sofic shift.
12:05 Session 2A Chair: Alexander Shen Session 2B Chair: Christoph Durr
Lance Fortnow, Troy Lee and Nikolai Vereshchagin.Kolmogorov complexity with error.Stephanie Wehner.Entanglement in Interactive Proof Systems with Binary Answers.
Bjoern Kjos-Hanssen, Wolfgang Merkle and Frank Stephan.Kolmogorov complexity and the recursion theorem.Andris Ambainis and Robert Spalek.Quantum Algorithms for Matching and Network Flows.
14:30 Session 3A Chair: Christoph Durr Session 3B Chair: Markus Lohrey
Wojciech Rytter.The Number of Runs in a String: Improved Analysis of of the Linear Upper Bound.Sebastian Aland, Dominic Dumrauf, Martin Gairing, Burkhard Monien and Florian Schoppmann.Exact Price of Anarchy for Polynomial Congestion Games.
Amit Chakrabarti, Khanh Do Ba and S. Muthukrishnan.Estimating Entropy and Entropy Norm on Data Streams.Venkatesan Chakaravarthy and Sambuddha Roy.Oblivious Symmetric Alternation.
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.Tzur Sayag, Shai Fine and Yishay Mansour.Combining Multiple Heuristics.
15:45Coffee break
16:15 Session 4A Chair: Alexander Zvonkin Session 4B Chair: Wolfgang Thomas
Khaled Elbassioni and Nabil Mustafa.Conflict-Free Colorings of Rectangle Ranges.Vince Barany.Invariants of automatic presentations and semi-synchronous transductions.
Mirela Damian, Robin Flatland and Joseph O'Rourke.Grid Vertex-Unfolding Orthogonal Polyhedra.Olivier Finkel.On the Accepting Power of $2$-Tape B\"uchi Automata.
Bin Fu.Theory and Application of Width Bounded Geometric Separator.Ina Maeurer.Weighted Picture Automata and Weighted Logics.

Friday February 24, 2006

09:00 Plenary Session: Invited Talk Leonid LevinSymmetry Breaking in Computing Media
Updated version of the paper: arXiv:cs.DC/0512077 (version 2, 22 Feb 2006)
(Gene Itkis, Leonid Levin. Flat Holonomies on Automata Networks)
Chair: Alexander Shen
10:00Coffee break
10:30 Session 5A Chair: Miklos Santha Session 5B Chair: Pierre Fraignaud
Krishnendu Chatterjee, Rupak Majumdar and Thomas A. Henzinger.Markov Decision Processes with Multiple Objectives.Josep Diaz and Dimitrios Thilikos.Fast FPT-algorithms for cleaning grids.
Paolo Penna and Carmine Ventre.The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms.Chinmoy Dutta and Jaikumar Radhakrishnan.Tradeoffs in depth-two superconcentrators.
George Christodoulou, Vahab Mirrokni and Anastasios Sidiropoulos.Convergence and Approximation in Potential Games.Vikraman Arvind and Johannes Koebler.On Hypergraph and Graph Isomorphism with Bounded Color Classes.
11:55 Session 6A Chair: Alexander Zvonkin Session 6B Chair: Jean-Eric Pin
Maxim Ushakov and Andrey Rumyantsev.Forbidden substrings, Kolmogorov complexity and almost periodic sequences.Vince Barany, Christof Loeding and Olivier Serre.Regularity Problems for Visibly Pushdown Languages.
John Hitchcock.Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets.Georg Schnitger.Regular expressions and NFAs without epsilon-transitions.
14:30 Session 7A Chair: Jacobo Toran Session 7B Chair: Luc Segoufin
Christian Glaßer, Aduri Pavan, Alan L. Selman and Liyu Zhang.Redundancy in Complete Sets.Joost Engelfriet and Hendrik Jan Hoogeboom.Nested Pebbles and Transitive Closure.
Harry Buhrman, Leen Torenvliet and Falk Unger.Sparse selfreducible sets and polynomial size circuit lower bounds.Amitabha Roy and Howard Straubing.Definability of Languages by Generalized First-Order Formulas over (N,+).
Adam Klivans and Lance Fortnow.Linear Advice for Randomized Logarithmic Space.Michael Bauland, Edith Hemaspaandra, Ilka Johannsen and Henning Schnoor.Generalized Modal Satisfiability.
15:45Coffee break
16:15 Session 8A Chair: Pascal Weil Session 8B Chair: Jacobo Toran
Krishnendu Chatterjee and Thomas A. Henzinger.Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games.Reuven Cohen and David Peleg.Convergence of Autonomous Mobile Robots With Inaccurate Sensors and Movements.
Dietmar Berwanger, Anuj Dawar, Paul Hunter and Stephan Kreutzer.DAG-Width and Parity Games.Daniel Mölle, Stefan Richter and Peter Rossmanith.A Faster Algorithm for the Steiner Tree Problem.
Andrei Romashchenko.Reliable Computations Based on Locally Decodable Codes.Benjamin Doerr.Generating Randomized Roundings with Cardinality Constraints and Derandomizations.
Conference Dinner

Saturday February 25, 2006

09:00Plenary Session: Invited TalkHelmut SeidlInterprocedurally Analyzing Polynomial Identities Chair: Wolfgang Thomas
10:00Coffee break
10:30 Session 9A Chair: Peter Sanders Session 9B Chair: Markus Lohrey
Vinayaka Pandit and Rohit Khandekar.Online Sorting Buffers on Line.Susanne Albers and Hiroshi Fujiwara.Energy-Efficient Algorithms for Flow Time Minimization.
Yossi Azar and Yoel Chaiutin.Optimal Node Routing.Kousha Etessami and Mihalis Yannakakis.Efficient Analysis of Classes of Recursive Markov Decision Processes and Stochastic Games.
Dimitris Fotakis.Memoryless Facility Location in One Pass.Manuel Bodirsky and Victor Dalmau.Datalog and Constraint Satisfaction with Infinite Templates.
11:55 Session 10A Chair: Jacobo Toran Session 10B Chair: Paul Gastin
Nutan Limaye, Meena Mahajan and Jayalal Sarma M N.Evaluating Monotone Circuits on Cylinders, Planes and Torii.Dietrich Kuske.Weighted asynchronous cellular automata.
Alexander Healy and Emanuele Viola.Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two.Darin Goldstein and Kojiro Kobayashi.On the Complexity of the "Most General" Firing Squad Synchronization Problem.
Webmaster, Last modified march 13th, 2006 [html] [css]