32nd International Symposium on

Mathematical Foundations of Computer Science

August 26 – August 31, 2007


Program

Sunday August 26, 2007

16:00 – 21:00Registration

Monday August 27, 2007

8:00 – 9:00Registration
9:00 – 9:05Opening (Jesuit Hall)
9:05 – 9:55KEYNOTE (Jesuit Hall)
Ludek Kucera
9:05 – 9:55Minimum Cycle Bases in Graphs Algorithms and Applications
Kurt Mehlhorn
9:55 – 10:00Short Break
10:00 – 11:00SESSION A - RANDOM GRAPHS (Jesuit Hall)
Chair: Ludek Kucera
10:00 – 10:30Expander Properties and the Cover Time of Random Intersection Graphs
Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis
10:30 – 11:00Uncover Low Degree Vertices and Minimise the Mess: Independent Sets in Random Regular Graphs
William Duckworth and Michele Zito
10:00 – 11:00SESSION B - REWRITING (Hall B)
Chair: Antonin Kucera
10:00 – 10:30Transition Graphs of Rewriting Systems over Unranked Trees
Alex Spelten and Christof Löding
10:30 – 11:00Rewriting Conjunctive Queries Determined by Views
Foto Afrati
11:00 – 11:30Coffee Break
11:30 – 13:00SESSION A - APPROXIMATION ALGORITHMS (Jesuit Hall)
Chair: Ludek Kucera
11:30 – 12:00Approximation Algorithms for the Maximum Internal Spanning Tree Problem
Gabor Salamon
12:00 – 12:30New Approximability Results for 2-Dimensional Packing Problems
Claus Jansen and Roberto Solis-Oba
12:30 – 13:00On Approximation of Bookmark Assignments
Yuichi Asahiro, Eiji Miyano, Toshihide Murata and Hirotaka Ono
11:30 – 13:00SESSION B - AUTOMATA AND CIRCUITS (Hall B)
Chair: Antonin Kucera
11:30 – 12:00Height-Deterministic Pushdown Automata
Dirk Nowotka and Jiri Srba
12:00 – 12:30Minimizing Variants of Visibly Pushdown Automata
Patrick Chervet and Igor Walukiewicz
12:30 – 13:00Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids
Andreas Krebs, Christoph Behle and John Mark Mercer
13:00 – 14.30Lunch Break
14:30 – 16:00SESSION A - COMPLEXITY AND GRAPHS (Jesuit Hall)
Chair: Kurt Mehlhorn
14:30 – 15:00Exact Algorithms for L(2,1)-labeling of Graphs
Jan Kratochvil, Dieter Kratsch and Mathieu Liedloff
15:00 – 15:30On (k,l)-Leaf Powers
Andreas Brandstadt and Peter Wagner
15:30 – 16:00The Complexity of Solitaire
Pierre McKenzie and Luc Longpré
16:00 – 16:30Coffee Break
16:30 – 17:30SESSION A - ALGORITHMS (Jesuit Hall)
Chair: Kurt Mehlhorn
16:30 – 17:00Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems
Camil Demetrescu, Bruno Escoffier, Gabriel Moruz and Andrea Ribichini
17:00 – 17:30Space-Conscious Compression
Travis Gagie and Giovanni Manzini
18.30Meeting Point for Costuming to Welcome Rozmberg Dinner
20:00 – 22:30Welcome Rozmberg Dinner

Tuesday August 28, 2007

9:00 – 9:55KEYNOTE (Jesuit Hall)
Antonin Kucera
9:00 – 9:55Hierarchies of Infinite Structures Generated by Pushdown Automata and Recursion Schemes
Luke Ong
9:55 – 10:00Short Break
10:00 – 11:00SESSION A - GRAPHS (Jesuit Hall)
Chair: Leslie Valiant
10:00 – 10:30Small Alliances in Graphs
Rodolfo Carvajal, Martín Matamala, Nicolás Schabanel and Iván Rapaport
10:30 – 11:00Dynamic Matchings in Convex Bipartite Graphs
Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen and Irit Katriel
10:00 – 11:00SESSION B - ITERATION AND RECURSION (Hall B)
Chair: Luke Ong
10:00 – 10:30What are Iteration Theories?
Jiri Adamek, Stefan Milius and Jiri Velebil
10:30 – 11:00Properties Complementary to Program Self-Reference
John Case and Samuel Moelius
11:00 – 11:30Coffee Break
11:30 – 13:00SESSION A - ALGORITHMS (Jesuit Hall)
Chair: Leslie Valiant
11:30 – 12:00A Linear Time Algorithm for the k Maximal Sums Problem
Gerth Stølting Brodal and Allan Grønlund Jørgensen
12:00 – 12:30On The Complexity of Computing Treelength
Daniel Lokshtanov
12:30 – 13:00On Time Lookahead Algorithms for the Online Data Acknowledgement Problem
Csanad Imreh and Tamas Nemet
11:30 – 13:00SESSION B - AUTOMATA (Hall B)
Chair: Luke Ong
11:30 – 12:00Real Time Language Recognition on 2D Cellular Automata: Dealing with Non-Convex Neighborhoods
Martin Delacourt and Victor Poupet
12:00 – 12:30Towards a Rice Theorem on Traces of Cellular Automata
Pierre Guillon and Julien Cervelle
12:30 – 13:00Progresses in the Analysis of Stochastic 2D Cellular Automata: a Study of Asynchronous 2D Minority
Damien Regnault, Nicolas Schabanel and Eric Thierry
13:00 – 14.30Lunch Break
14:30 – 16:00SESSION A - COMPLEXITY (Jesuit Hall)
Chair: Joaquin Gabarro
14:30 – 15:00Hard Problems on Quadratic Forms and a New Cryptographic Primitive
Rupert J. Hartung and Claus-Peter Schnorr
15:00 – 15:30Reachability Problems in Quaternion Matrix and Rotation Semigroups
Paul Bell and Igor Potapov
15:30 – 16:00VPSPACE and a Transfer Theorem over the Complex Field
Pascal Koiran and Sylvain Perifel
16:00 – 16:30Coffee Break
16:30 – 17:30SESSION A - PROTOCOLS (Jesuit Hall)
Chair: Joaquin Gabarro
16:30 – 17:00Efficient Provably-Secure Hierarchical Key Assignment Schemes
Alfredo De Santis, Anna Lisa Ferrara and Barbara Masucci
17:00 – 17:30Nearly Private Information Retrieval
Amit Chakrabarti and Anna Shubina

Wednesday August 29, 2007

9:00 – 9:55KEYNOTE (Jesuit Hall)
Ludek Kucera
9:00 – 9:55Evolvability
Leslie G. Valiant
9:55 – 10:00Short Break
10:00 – 11:00SESSION A - GRAPHS (Jesuit Hall)
Chair: Branislav Rovan
10:00 – 10:30Packing and Squeezing Subgraphs into Planar Graphs
Fabrizio Frati, Markus Geyer and Michael Kaufmann
10:30 – 11:00The Maximum Solution Problem on Graphs
Peter Jonsson, Gustav Nordh and Johan Thapper
11:00 – 11:30Coffee Break
11:30 – 13:00SESSION A - ALGORITHMS (Jesuit Hall)
Chair: Branislav Rovan
11:30 – 12:00Dobrushin Conditions for Systematic Scan with Block Dynamics
Kasper Pedersen
12:00 – 12:30A Lower Bound of 1+φ for Truthful Scheduling
Elias Koutsoupias and Angelina Vidali
12:30 – 13:00Analysis of Maximal Repetitions in Strings
Maxime Crochemore and Lucian Ilie
11:30 – 13:00SESSION B - LANGUAGES (Hall B)
Chair: John Case
11:30 – 12:00Series-Parallel Languages on Scattered and Countable Posets
Nicolas Bedon and Chloé Rispal
12:00 – 12:30Traces of Term-Automatic Graphs
Antoine Meyer
12:30 – 13:00State Complexity of Basic Operations on Suffix-Free Regular Languages
Yo-Sub Han and Kai Salomaa
13:00 – 14.00Lunch Break
14.00Meeting Point for Discovering UNESCO City & BBQ

Thursday August 30, 2007

9:00 – 9:55KEYNOTE (Jesuit Hall)
Ludek Kucera
9:00 – 9:55Finite Model Theory on Tame Classes of Structures
Anuj Dawar
9:55 – 10:00Short Break
10:00 – 11:00SESSION A - COMPLEXITY (Jesuit Hall)
Chair: Vasek Chvatal
10:00 – 10:30Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete – A New Dichotomy Conjecture
Jaroslav Nesetril and Mark Siggers
10:30 – 11:00NP by Means of Lifts and Shadows
Gabor Kun and Jaroslav Nesetril
10:00 – 11:00SESSION B - QUANTUM COMPUTING (Hall B)
Chair: Anuj Dawar
10:00 – 10:30An Improved Claw Finding Algorithm Using Quantum Walk
Seiichiro Tani
10:30 – 11:00Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument
Rahul Tripathi
11:00 – 11:30Coffee Break
11:30 – 13:00SESSION A - GAME EQUILIBRIA (Jesuit Hall)
Chair: Maxime Crochemore
11:30 – 12:00Well Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach
Spyros Kontogiannis and Paul Spirakis
12:00 – 12:30Selfish Load Balancing under Partial Knowledge
Elias Koutsoupias, Panagiota Panagopoulou and Paul Spirakis
12:30 – 13:00Extending the Notion of Rationality of Selfish Agents: Second Order Nash Equilibria
Vittorio Bilo' and Michele Flammini
11:30 – 13:00SESSION B - ISOMORPHISM (Hall B)
Chair: Anuj Dawar
11:30 – 12:00On the Complexity of Game Isomorphism
Joaquim Gabarro, Maria Serna and Alina Garcia
12:00 – 12:30Hardness Results for Tournament Isomorphism and Automorphism
Fabian Wagner
12:30 – 13:00Relating Complete and Partial Solution for Problems Similar to Graph Automorphism
Takayuki Nagoya and Seinosuke Toda
13:00 – 14.30Lunch Break
14:30 – 16:00SESSION A - GAMES (Jesuit Hall)
Chair: Peter Widmayer
14:30 – 15:00Congestion Games with Player-Specific Constants
Marios Mavronicolas, Igal Milchtaich, Burkhard Monien and Karsten Tiemann
15:00 – 15:30Finding Patterns In Given Intervals
Maxime Crochemore, Costas Iliopoulos and M Sohel Rahman
15:30 – 16:00The Power of Two Prices: Beyond Cross-Monotonicity
Yvonne Bleischwitz, Burkhard Monien, Florian Schoppmann and Karsten Tiemann
16:00 – 16:30Coffee Break
16:30 – 17:30SESSION A - ALGEBRA + STRINGS (Jesuit Hall)
Chair: Peter Widmayer
16:30 – 17:00Semisimple Algebras of Almost Minimal Rank over the Reals
Markus Bläser and Andreas Meyer
17:00 – 17:30Structural Analysis of Gapped Motifs of a String
Esko Ukkonen

Friday August 31, 2007

9:00 – 9:55KEYNOTE (Jesuit Hall)
Ludek Kucera
9:00 – 9:55How To Be Fickle
Vašek Chvátal
9:55 – 10:00Short Break
10:00 – 11:00SESSION A - NETWORKS (Jesuit Hall)
Chair: Paul Spirakis
10:00 – 10:30Communication in Networks with Random Dependent Faults
Evangelos Kranakis, Michel Paquette and Andrzej Pelc
10:30 – 11:00Optimal Gossiping in Directed Geometric Radio Networks in Presence of Dynamical Faults
Andrea Clementi, Angelo Monti, Francesco Pasquale and Riccardo Silvestri
11:00 – 11:30Coffee Break
11:30 – 13:00SESSION A - ALGORITHMS (Jesuit Hall)
Chair: Paul Spirakis
11:30 – 12:00Online and Offline Access to Short Lists
Torben Hagerup
12:00 – 12:30Optimal Randomized Comparison Based Algorithms for Collision
Riko Jacob
12:30 – 13:00Randomized and Approximation Algorithms for Blue-Red Matching
Christos Nomikos, Aris Pagourtzis and Stathis Zachos
13:00 – 14.30Lunch Break
14:30 – 16:00SESSION A - WORDS AND GRAPHS (Jesuit Hall)
Chair: Ludek Kucera
14:30 – 15:00Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation
Klaus Meer and Martin Ziegler
15:00 – 15:30Finding Paths Between Graph Colourings: PSPACE-completeness and Superpolynomial Distances
Paul Bonsma and Luis Cereceda
15:30 – 16:00Shuffle Expressions and Words with Nested Data
Mikolaj Bojanczyk and Henrik Bjorklund
16:00 – 16:15Closing

Modified: 31 Aug 2007