program

Each contributed talk will last 25 minutes, including discussion. A printed version of the program will be available at the conference.

Wednesday February 21, 2007

19:00-22:00 Get-Together and Registration
small snacks and drinks
Forum M of Mayersche Buchhandlung, Centre of town

Thursday February 22, 2007

8:00Registration
(the registration desk will be open throughout the conference)
8:45Opening
9:00-10:00 Invited Talk Moshe Y. Vardi The Büchi Complementation Saga. slides (ps)
Coffee break
10:25-11:40
Session 1ASession 1B
Bruno Courcelle and Andrew Twigg. Compact Forbidden-set Routing. slides (pdf) Olivier Carton, Jean Berstel, Luc Boasson and Isabelle Fagnot. A First Investigation of Sturmian trees. slides (pdf)
Manfred Kunde. A new bound for pure greedy hot potato routing. Sylvain Lombardy. On the Size of the Universal Automaton of a Regular Language. slides (pdf)
Ioannis Caragiannis. Wavelength management in WDM rings to maximize the number of connections. Francine Blanchet-Sadri, Joshua Gafni and Kevin Wilson. Correlations of Partial Words.
Coffee break
12:00-12:50
Session 2ASession 2B
Eldar Fischer and Orly Yahalom. Testing Convexity Properties of Tree Colorings. slides (pdf) Peter Bürgisser. On defining integers in the counting hierarchy and proving arithmetic circuit lower bounds. slides (pdf)
Amin Coja-Oghlan, Michael Krivelevich and Dan Vilenchik. Why almost all k-colorable graphs are easy. slides (ppt) Troy Lee. A new rank technique for formula size lower bounds. slides (pdf)
Lunch
14:15-15:30
Session 3ASession 3B
Ilan Newman and Yuri Rabinovich. Hard Metrics from Cayley Graphs of Abelian Groups. slides (pdf) Dietmar Berwanger. Admissibility in infinite games. slides (pdf)
Robert Elsässer and Thomas Sauerwald. Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs. Hugo Gimbert. Pure stationary optimal strategies in Markov decision processes.
Adrian Dumitrescu and Csaba Tóth. Light Orthogonal Networks with Constant Geometric Dilation. Felix Brandt, Felix Fischer and Markus Holzer. Symmetries and the Complexity of Pure Nash Equilibrium. slides (pdf)
Coffee break
15:50-16:40
Session 4ASession 4B
Daniel Král. Computing representations of matroids of bounded branch-width. slides (pdf) Christian Glaßer, Alan L. Selman, Stephen Travers and Klaus W. Wagner. The Complexity of Unions of Disjoint Sets. slides (pdf)
Pinar Heggernes, Karol Suchan, Ioan Todinca and Yngve Villanger. Characterizing minimal interval completions: Towards better understanding of profile and pathwidth. slides (pdf) Laurent Bienvenu. Kolmogorov-Loveland stochasticity and Kolmogorov complexity. slides (pdf)
Coffee break
17:00-17:50
Session 5ASession 5B
Sören Laue and Stefan Funke. Bounded-hop energy-efficient Broadcast in low-dimensional Metrics via Coresets. Javier Esparza, Stefan Kiefer and Michael Luttenberger. On Fixed Point Equations over Commutative Semirings. slides (pdf)
Christian Hundt and Maciej Liskiewicz. On the Complexity of Affine Image Matching. slides (ppt) Andrea Sattler-Klein. An Exponential Lower Bound For Prefix Gröbner Bases in Free Monoid Rings.
18:00 Short presentation on Aachen Cathedral, Visit of Cathedral
19:00 Reception in the Town Hall, Krönungssaal

Friday February 23, 2007

9:00-10:00 Invited Talk Dorothea Wagner Speed-Up Techniques for Shortest-Path Computations. slides (pdf)
Coffee break
10:25-11:40
Session 6ASession 6B
Hans Bodlaender. A Cubic Kernel for Feedback Vertex Set. slides (pdf) Enrico Formenti and Petr Kurka. A search algorithm for the maximal attractor of a cellular automaton.
Peter Damaschke. The Union of Minimal Hitting Sets: Parameterized Combinatorial Bounds and Counting. slides (pdf) Grégory Lafitte and Michaël Weiss. Universal Tilings. slides (pdf)
Marc Tedder and Derek Corneil. An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs. Alberto Bertoni, Massimiliano Goldwurm and Violetta Lonati. On the complexity of unary tiling-recognizable picture languages. slides (pdf)
Coffee break
12:00-12:50
Session 7ASession 7B
Hans Ulrich Simon. A Characterization of Strong Learnability in the Statistical Query Model. Pascal Koiran and Sylvain Perifel. VPSPACE and a transfer theorem over the reals. slides (pdf)
Jan Poland. On the Consistency of Discrete Bayesian Learning. slides (pdf) Jin-Yi Cai and Pinyan Lu. On Symmetric Signatures in Holographic Algorithms.
Lunch
14:15-15:30
Session 8ASession 8B
Benjamin Doerr. Randomly Rounding Rationals with Cardinality Constraints and Derandomizations. Nutan Limaye, Meena Mahajan and Raghavendra Rao. Arithmetizing Classes arround NC1 and L. slides (pdf)
Chien-Chung Huang. Cheating to Get Better Roommates in a Random Stable Matching. Manindra Agrawal, Thanh Minh Hoang and Thomas Thierauf. The polynomially bounded perfect matching problem is in NC2 slides (pdf)
Costas Busch and Srikanta Tirthapura. A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window. slides (ppt) Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson and Denis Thérien. Languages with bounded multiparty communication complexity. slides (ppt)
Coffee break
16:00-17:15
Session 9ASession 9B
Telikepalli Kavitha, Kurt Mehlhorn and Dimitrios Michail. New Approximation Algorithms for Minimum Cycle Bases of Graphs. Davide Bresolin, Angelo Montanari and Pietro Sala. An optimal tableau-based decision algorithm for Propositional Neighborhood Logic. slides (pdf)
Iman Hajirasouliha, Hossein Jowhari, Ravi Kumar and Ravi Sundaram. On Completing Latin Squares. slides (ppt) Thomas Schwentick and Volker Weber. Bounded-Variable Fragments of Hybrid Logics. slides (pdf)
Artur Czumaj and Christian Sohler. Small Space Representations for Metric Min-Sum k-Clustering and their Applications. Lutz Schröder and Dirk Pattinson. Rank-1 Modal Logics are Coalgebraic.
17:45 Departure to Conference Dinner from the Conference Venue
19:00-23:00 Conference Dinner
Kasteel Bloemendal, Vaals

Saturday February 24, 2007

9:00-10:00 Invited Talk Serge Abiteboul A Calculus and Algebra for Distributed Data Management. slides (ppt)
Coffee break
10:25-11:40
Session 10ASession 10B
Gábor Ivanyos, Miklos Santha and Luc Sanselme. An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups. slides (pdf) Mikolaj Bojanczyk and Piotr Hoffman. Reachability in Unions of Commutative Rewriting Systems is Decidable. slides (swf)
Andrew Childs, Aram Harrow and Pawel Wocjan. Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem. slides (pdf) Sergiu Bursuc, Hubert Comon-Lundh and Stéphanie Delaune. Associative-Commutative Deducibility Constraints. slides (pdf)
Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond and Shigeru Yamashita. Quantum Network Coding. Ralf Küsters and Tomasz Truderung. On the Automatic Analysis of Recursive Security Protocols with XOR. slides (pdf)
Coffee break
12:00-12:50
Session 11ASession 11B
Iftah Gamzu and Danny Segev. Improved Online Algorithms for the Sorting Buffer Problem. Oleg Verbitsky. Planar graphs: Logical complexity and parallel isomorphism tests. slides (pdf)
Janina Brenner and Guido Schäfer. Cost Sharing Methods for Makespan and Completion Time Scheduling. Henning Schnoor and Ilka Schnoor. Enumerating all Solutions for Constraint Satisfaction Problems. slides (pdf)
Lunch