CONFERENCE SPEECHES

Day 1 - 25.08.2008
Invited Lecture:

• Algebraic Graph Algorithms by Piotr Sankowski

Contributed Speeches:

• Complexity of Data Tree Patterns over XML Documents by Claire David
• Optimizing Conjunctive Queries over Trees using Schema Information by Henrik Björklund
• Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise by Bodo Manthey
• Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control by Gábor Erdélyi
• A Note on k-colourability of P_5-free Graphs by Marcin Kamiński
• Colouring Random Empire Trees by Michele Zito
• The Height of Factorization Forests by Manfred Kufleitner
• Succinctness of Regular Expressions with Interleaving, Intersection and Counting by Wouter Gelade

Day 2 - 26.08.2008
Invited Lecture:

• A Robust Class of Regular Languages by Jean-Éric Pin

Contributed Speeches:

• Complexity and Asymptotic Density of Boolean Functions over Implication by Antoine Genitrini
• Monadic Second Order Logic on Graphs with Local Cardinality Constraints by Stefan Szeider
• Directed Percolation Arising in Stochastic Cellular Automata Analysis by Damien Regnault
• Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems by Michael Elberfel
• When Ignorance Helps: Graphical Multicast Cost Sharing Games by Vittorio Bilo
• Voronoi Games on Cycle Graphs by Florian Schoppmann
• Reversal-Bounded Counter Machines Revisited by Arnaud Sangnier
• On the Decidability of Bounded Valuedness for Transducers by Rodrigo de Souza

Day 3 - 27.08.2008
Invited Lecture:

• On Synchronous and Asynchronous Interaction in Distributed Systems by Ursula Goltz

Contributed Speeches:

• On the Shortest Linear Straight-line Program for Computing Linear Forms by Joan Boyar
• Clustering with Partial Information by Federico Mancini
• From Lambda Calculus to Universal Algebra and Back by Giulio Manzonetto
• Short Proofs of Strong Normalization by Aleksander Wojdyga
• Nilpotency and Limit Sets of Cellular Automata by Gaétan Richard
• Periodicity and Immortality in Reversible Computing by Nicolas Ollinger
• Positional Strategies for Higher-Order Pushdown Parity Games by Michaela Slaats
• Question/Answer Games on Towers and Pyramids by Numan Sheikh

Day 4 - 28.08.2008
Invited Lecture:

• One Useful Logic That Defines Its Own Truth by Yuri Gurevich

Contributed Speeches:

• A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem by Gianpiero Monaco
• Approximating Independent Set and Coloring in Random Uniform Hypergraphs by Kai Plociennik
• A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs by Petr A. Golovach
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs by Maurice J. Jansen
• Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae by B. V. Raghavendra Rao
• Computing Sharp 2-Factors in Claw-Free Graphs by Daniël Paulusma
• Reoptimization of the Metric Deadline TS by Dennis Komm
• Regional Languages and Tiling: a Unifying Approach to Picture Grammars by Matteo Pradella
• A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems by Emilie Charlier

Day 5 - 29.08.2008
Invited Lecture:

• Deterministic Models of Communication Faults by Rastislav Královič

Contributed Speeches:

• Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations by Christian Hundt
• Flip Algorithm for Segment Triangulations by Mathieu Brévilliers
• A Random Oracle Does Not Help Extract the Mutual Information by Andrei Romashchenko
• Arthur and Merlin as Oracles by Sambuddha Roy
• Shortest Synchronizing Strings for Huffman Codes by Marek Biskup
• On a Special Class of Primitive Words by Elena Czeizler
• The Maximum Independent Set Problem in Planar Graphs by Martin Milanič
• Iterative Compression and Exact Algorithms by Serge Gaspers