Print version (pdf).


Sunday, August 24
15:00 19:00 Registration

Monday, August 25
7:00 9:00 Registration
9:00 9:30 Complexity of Data Tree Patterns over XML Documents
Claire David
9:30 10:00 Optimizing Conjunctive Queries over Trees using Schema Information
Henrik Björklund, Wim Martens and Thomas Schwentick
10:00 10:30 Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
Bodo Manthey and Till Tantau
10:30 11:00 Coffee Break
11:00 11:30 Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control
Gábor Erdélyi, Markus Nowak and Jörg Rothe
11:30 12:00 Step-out Ring Signatures
Marek Klonowski, £ukasz Krzywiecki, Miros³aw Kuty³owski and Anna Lauks
12:00 12:10 Cigarette Break
Invited Lecture by Piotr Sankowski
12:10 13:10 Algebraic Graph Algorithms
Piotr Sankowski
13:10 - 15:30 free time 13:10 - 15:30
15:30 16:00 A Note on k-colourability of P_5-free Graphs
Chinh T. Hoáng, Marcin Kamiñski, Vadim Lozin, Joe Sawada and Xiao Shu
16:00 16:30 Colouring Random Empire Trees
Andrew R. McGrae and Michele Zito
16:30 17:00 Coffee Break
Languages I
17:00 17:30 The Height of Factorization Forests
Manfred Kufleitner
17:30 18:00 Succinctness of Regular Expressions with Interleaving, Intersection and Counting
Wouter Gelade
18:10 welcome party 18:10

Tuesday, August 26
Logic I
9:00 9:30 A Complete Axiomatic System for a Process-Based Spatial Logic
Radu Mardare and Alberto Policriti
9:30 10:00 Complexity and Asymptotic Density of Boolean Functions over Implication
Hervé Fournier, Daniele Gardy, Antoine Genitrini and Bernhard Gittenberger
10:00 10:30 Monadic Second Order Logic on Graphs with Local Cardinality Constraints
Stefan Szeider
10:30 11:00 Coffee Break
11:00 11:30 Directed Percolation Arising in Stochastic Cellular Automata Analysis
Damien Regnault
11:30 12:00 Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems
Michael Elberfeld and Till Tantau
12:00 12:10 Cigarette Break
Invited Lecture by Jean-Éric Pin
12:10 13:10 A Robust Class of Regular Languages
Antonio Cano Gómez and Jean-Éric Pin
13:10 - 15:30 free time 13:10 - 15:30
Games I
15:30 16:00 When Ignorance Helps: Graphical Multicast Cost Sharing Games
Vittorio Bilo, Angelo Fanelli, Michele Flammini and Luca Moscardelli
16:00 16:30 Voronoi Games on Cycle Graphs
Marios Mavronicolas, Burkhard Monien, Vicky G. Papadopoulou and Florian Schoppmann
16:30 17:00 Coffee Break
Automata and Machines I
17:00 17:30 Reversal-Bounded Counter Machines Revisited
Alain Finkel and Arnaud Sangnier
17:30 18:00 On the Decidability of Bounded Valuedness for Transducers
Jacques Sakarovitch and Rodrigo de Souza
18:30 Torunian gingerbreads in Copernicus House - Group 1

Wednesday, August 27
9:00 9:30 On the Shortest Linear Straight-line Program for Computing Linear Forms
Joan Boyar, Philip Matthews and René Peralta
9:30 10:00 Clustering with Partial Information
Hans L. Bodlaender, Michael R. Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos and Frances A. Rosamond
10:00 10:30 A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
Daniel Raible and Henning Fernau
10:30 11:00 Coffee Break
Logic II
11:00 11:30 From Lambda Calculus to Universal Algebra and Back
Giulio Manzonetto and Antonino Salibra
11:30 12:00 Short Proofs of Strong Normalization
Aleksander Wojdyga
12:00 12:10 Cigarette Break
Invited Lecture by Ursula Goltz
12:10 13:10 On Synchronous and Asynchronous Interaction in Distributed Systems
Rob van Glabbeek, Ursula Goltz and Jens-Wolfhard Schicke
13:10 - 15:30 free time 13:10 - 15:30
Automata and Machines II
15:30 16:00 Nilpotency and Limit Sets of Cellular Automata
Pierre Guillon and Gaétan Richard
16:00 16:30 Periodicity and Immortality in Reversible Computing
Jarkko Kari and Nicolas Ollinger
16:30 17:00 Coffee Break
Games II
17:00 17:30 Positional Strategies for Higher-Order Pushdown Parity Games
Arnaud Carayol and Michaela Slaats
17:30 18:00 Question/Answer Games on Towers and Pyramids
Sarmad Abbasi and Numan Sheikh
18:30 Torunian gingerbreads in Copernicus House - Group 2

Thursday, August 28
9:00 9:30 A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
Ioannis Caragiannis and Gianpiero Monaco
9:30 10:00 Approximating Independent Set and Coloring in Random Uniform Hypergraphs
Kai Plociennik
10:00 10:30 A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
Feodor F. Dragan, Fedor V. Fomin and Petr A. Golovach
10:30 11:00 Coffee Break
11:00 11:30 Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
Maurice J. Jansen
11:30 12:00 Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
Meena Mahajan and B. V. Raghavendra Rao
12:00 12:10 Cigarette Break
Invited Lecture by Yuri Gurevich
12:10 13:10 One Useful Logic That Defines Its Own Truth
Andreas Blass and Yuri Gurevich
13:10 - 15:30 free time 13:10 - 15:30
Around NP I
15:30 16:00 Computing Sharp 2-Factors in Claw-Free Graphs
Hajo Broersma and Daniël Paulusma
16:00 16:30 Reoptimization of the Metric Deadline TSP
Hans-Joachim Böckenhauer and Dennis Komm
16:30 17:00 Coffee Break
Languages II
17:00 17:30 Regional Languages and Tiling: a Unifying Approach to Picture Grammars
Alessandra Cherubini, Stefano Crespi Reghizzi and Matteo Pradella
17:30 18:00 A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems
Emilie Charlier and Michel Rigo
19:00 outdoor grill party 19:00

Friday, August 29
9:00 9:30 Resolution Width and Cutting Plane Rank are Incomparable
Mark Rhodes
9:30 10:00 Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations
Christian Hundt and Maciej Li¶kiewicz
10:00 10:30 Flip Algorithm for Segment Triangulations
Mathieu Brévilliers, Nicolas Chevallier and Dominique Schmitt
10:30 11:00 Coffee Break
11:00 11:30 A Random Oracle Does Not Help Extract the Mutual Information
Andrei Muchnik and Andrei Romashchenko
11:30 12:00 Arthur and Merlin as Oracles
Venkatesan T. Chakaravarthy and Sambuddha Roy
12:00 12:10 Cigarette Break
Invited Lecture by Rastislav Královiè
12:10 13:10 Deterministic Models of Communication Faults
Rastislav Královiè and Richard Královiè
13:10 - 15:30 free time 13:10 - 15:30
Languages III
15:30 16:00 Shortest Synchronizing Strings for Huffman Codes
Marek Biskup
16:00 16:30 On a Special Class of Primitive Words
Elena Czeizler, Lila Kari and Shinnosuke Seki
16:30 17:00 Coffee Break
Around NP II
17:00 17:30 The Maximum Independent Set Problem in Planar Graphs
Vladimir E. Alekseev, Vadim Lozin, Dmitriy Malyshev and Martin Milaniè
17:30 18:00 Iterative Compression and Exact Algorithms
Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff and Saket Saurabh
the end