32nd International Symposium on
Mathematical Foundations of Computer Science
August 26 – August 31, 2007
Program
Sunday August 26, 2007
| 16:00 – 21:00 | Registration |
Monday August 27, 2007
| 8:00 – 9:00 | Registration |
| 9:00 – 9:05 | Opening (Jesuit Hall) |
| 9:05 – 9:55 | KEYNOTE (Jesuit Hall) Ludek Kucera |
| 9:05 – 9:55 | Minimum Cycle Bases in Graphs Algorithms and Applications Kurt Mehlhorn |
| 9:55 – 10:00 | Short Break |
| 10:00 – 11:00 | SESSION A - RANDOM GRAPHS (Jesuit Hall) Chair: Ludek Kucera |
| 10:00 – 10:30 | Expander Properties and the Cover Time of Random Intersection Graphs Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis |
| 10:30 – 11:00 | Uncover Low Degree Vertices and Minimise the Mess: Independent Sets in Random Regular Graphs William Duckworth and Michele Zito |
| 10:00 – 11:00 | SESSION B - REWRITING (Hall B) Chair: Antonin Kucera |
| 10:00 – 10:30 | Transition Graphs of Rewriting Systems over Unranked Trees Alex Spelten and Christof Löding |
| 10:30 – 11:00 | Rewriting Conjunctive Queries Determined by Views Foto Afrati |
| 11:00 – 11:30 | Coffee Break |
| 11:30 – 13:00 | SESSION A - APPROXIMATION ALGORITHMS (Jesuit Hall) Chair: Ludek Kucera |
| 11:30 – 12:00 | Approximation Algorithms for the Maximum Internal Spanning Tree Problem Gabor Salamon |
| 12:00 – 12:30 | New Approximability Results for 2-Dimensional Packing Problems Claus Jansen and Roberto Solis-Oba |
| 12:30 – 13:00 | On Approximation of Bookmark Assignments Yuichi Asahiro, Eiji Miyano, Toshihide Murata and Hirotaka Ono |
| 11:30 – 13:00 | SESSION B - AUTOMATA AND CIRCUITS (Hall B) Chair: Antonin Kucera |
| 11:30 – 12:00 | Height-Deterministic Pushdown Automata Dirk Nowotka and Jiri Srba |
| 12:00 – 12:30 | Minimizing Variants of Visibly Pushdown Automata Patrick Chervet and Igor Walukiewicz |
| 12:30 – 13:00 | Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids Andreas Krebs, Christoph Behle and John Mark Mercer |
| 13:00 – 14.30 | Lunch Break |
| 14:30 – 16:00 | SESSION A - COMPLEXITY AND GRAPHS (Jesuit Hall) Chair: Kurt Mehlhorn |
| 14:30 – 15:00 | Exact Algorithms for L(2,1)-labeling of Graphs Jan Kratochvil, Dieter Kratsch and Mathieu Liedloff |
| 15:00 – 15:30 | On (k,l)-Leaf Powers Andreas Brandstadt and Peter Wagner |
| 15:30 – 16:00 | The Complexity of Solitaire Pierre McKenzie and Luc Longpré |
| 16:00 – 16:30 | Coffee Break |
| 16:30 – 17:30 | SESSION A - ALGORITHMS (Jesuit Hall) Chair: Kurt Mehlhorn |
| 16:30 – 17:00 | Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems Camil Demetrescu, Bruno Escoffier, Gabriel Moruz and Andrea Ribichini |
| 17:00 – 17:30 | Space-Conscious Compression Travis Gagie and Giovanni Manzini |
| 18.30 | Meeting Point for Costuming to Welcome Rozmberg Dinner |
| 20:00 – 22:30 | Welcome Rozmberg Dinner |
Tuesday August 28, 2007
| 9:00 – 9:55 | KEYNOTE (Jesuit Hall) Antonin Kucera |
| 9:00 – 9:55 | Hierarchies of Infinite Structures Generated by Pushdown Automata and Recursion Schemes Luke Ong |
| 9:55 – 10:00 | Short Break |
| 10:00 – 11:00 | SESSION A - GRAPHS (Jesuit Hall) Chair: Leslie Valiant |
| 10:00 – 10:30 | Small Alliances in Graphs Rodolfo Carvajal, Martín Matamala, Nicolás Schabanel and Iván Rapaport |
| 10:30 – 11:00 | Dynamic Matchings in Convex Bipartite Graphs Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen and Irit Katriel |
| 10:00 – 11:00 | SESSION B - ITERATION AND RECURSION (Hall B) Chair: Luke Ong |
| 10:00 – 10:30 | What are Iteration Theories? Jiri Adamek, Stefan Milius and Jiri Velebil |
| 10:30 – 11:00 | Properties Complementary to Program Self-Reference John Case and Samuel Moelius |
| 11:00 – 11:30 | Coffee Break |
| 11:30 – 13:00 | SESSION A - ALGORITHMS (Jesuit Hall) Chair: Leslie Valiant |
| 11:30 – 12:00 | A Linear Time Algorithm for the k Maximal Sums Problem Gerth Stølting Brodal and Allan Grønlund Jørgensen |
| 12:00 – 12:30 | On The Complexity of Computing Treelength Daniel Lokshtanov |
| 12:30 – 13:00 | On Time Lookahead Algorithms for the Online Data Acknowledgement Problem Csanad Imreh and Tamas Nemet |
| 11:30 – 13:00 | SESSION B - AUTOMATA (Hall B) Chair: Luke Ong |
| 11:30 – 12:00 | Real Time Language Recognition on 2D Cellular Automata: Dealing with Non-Convex Neighborhoods Martin Delacourt and Victor Poupet |
| 12:00 – 12:30 | Towards a Rice Theorem on Traces of Cellular Automata Pierre Guillon and Julien Cervelle |
| 12:30 – 13:00 | Progresses in the Analysis of Stochastic 2D Cellular Automata: a Study of Asynchronous 2D Minority Damien Regnault, Nicolas Schabanel and Eric Thierry |
| 13:00 – 14.30 | Lunch Break |
| 14:30 – 16:00 | SESSION A - COMPLEXITY (Jesuit Hall) Chair: Joaquin Gabarro |
| 14:30 – 15:00 | Hard Problems on Quadratic Forms and a New Cryptographic Primitive Rupert J. Hartung and Claus-Peter Schnorr |
| 15:00 – 15:30 | Reachability Problems in Quaternion Matrix and Rotation Semigroups Paul Bell and Igor Potapov |
| 15:30 – 16:00 | VPSPACE and a Transfer Theorem over the Complex Field Pascal Koiran and Sylvain Perifel |
| 16:00 – 16:30 | Coffee Break |
| 16:30 – 17:30 | SESSION A - PROTOCOLS (Jesuit Hall) Chair: Joaquin Gabarro |
| 16:30 – 17:00 | Efficient Provably-Secure Hierarchical Key Assignment Schemes Alfredo De Santis, Anna Lisa Ferrara and Barbara Masucci |
| 17:00 – 17:30 | Nearly Private Information Retrieval Amit Chakrabarti and Anna Shubina |
Wednesday August 29, 2007
| 9:00 – 9:55 | KEYNOTE (Jesuit Hall) Ludek Kucera |
| 9:00 – 9:55 | Evolvability Leslie G. Valiant |
| 9:55 – 10:00 | Short Break |
| 10:00 – 11:00 | SESSION A - GRAPHS (Jesuit Hall) Chair: Branislav Rovan |
| 10:00 – 10:30 | Packing and Squeezing Subgraphs into Planar Graphs Fabrizio Frati, Markus Geyer and Michael Kaufmann |
| 10:30 – 11:00 | The Maximum Solution Problem on Graphs Peter Jonsson, Gustav Nordh and Johan Thapper |
| 11:00 – 11:30 | Coffee Break |
| 11:30 – 13:00 | SESSION A - ALGORITHMS (Jesuit Hall) Chair: Branislav Rovan |
| 11:30 – 12:00 | Dobrushin Conditions for Systematic Scan with Block Dynamics Kasper Pedersen |
| 12:00 – 12:30 | A Lower Bound of 1+φ for Truthful Scheduling Elias Koutsoupias and Angelina Vidali |
| 12:30 – 13:00 | Analysis of Maximal Repetitions in Strings Maxime Crochemore and Lucian Ilie |
| 11:30 – 13:00 | SESSION B - LANGUAGES (Hall B) Chair: John Case |
| 11:30 – 12:00 | Series-Parallel Languages on Scattered and Countable Posets Nicolas Bedon and Chloé Rispal |
| 12:00 – 12:30 | Traces of Term-Automatic Graphs Antoine Meyer |
| 12:30 – 13:00 | State Complexity of Basic Operations on Suffix-Free Regular Languages Yo-Sub Han and Kai Salomaa |
| 13:00 – 14.00 | Lunch Break |
| 14.00 | Meeting Point for Discovering UNESCO City & BBQ |
Thursday August 30, 2007
| 9:00 – 9:55 | KEYNOTE (Jesuit Hall) Ludek Kucera |
| 9:00 – 9:55 | Finite Model Theory on Tame Classes of Structures Anuj Dawar |
| 9:55 – 10:00 | Short Break |
| 10:00 – 11:00 | SESSION A - COMPLEXITY (Jesuit Hall) Chair: Vasek Chvatal |
| 10:00 – 10:30 | Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete – A New Dichotomy Conjecture Jaroslav Nesetril and Mark Siggers |
| 10:30 – 11:00 | NP by Means of Lifts and Shadows Gabor Kun and Jaroslav Nesetril |
| 10:00 – 11:00 | SESSION B - QUANTUM COMPUTING (Hall B) Chair: Anuj Dawar |
| 10:00 – 10:30 | An Improved Claw Finding Algorithm Using Quantum Walk Seiichiro Tani |
| 10:30 – 11:00 | Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument Rahul Tripathi |
| 11:00 – 11:30 | Coffee Break |
| 11:30 – 13:00 | SESSION A - GAME EQUILIBRIA (Jesuit Hall) Chair: Maxime Crochemore |
| 11:30 – 12:00 | Well Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach Spyros Kontogiannis and Paul Spirakis |
| 12:00 – 12:30 | Selfish Load Balancing under Partial Knowledge Elias Koutsoupias, Panagiota Panagopoulou and Paul Spirakis |
| 12:30 – 13:00 | Extending the Notion of Rationality of Selfish Agents: Second Order Nash Equilibria Vittorio Bilo' and Michele Flammini |
| 11:30 – 13:00 | SESSION B - ISOMORPHISM (Hall B) Chair: Anuj Dawar |
| 11:30 – 12:00 | On the Complexity of Game Isomorphism Joaquim Gabarro, Maria Serna and Alina Garcia |
| 12:00 – 12:30 | Hardness Results for Tournament Isomorphism and Automorphism Fabian Wagner |
| 12:30 – 13:00 | Relating Complete and Partial Solution for Problems Similar to Graph Automorphism Takayuki Nagoya and Seinosuke Toda |
| 13:00 – 14.30 | Lunch Break |
| 14:30 – 16:00 | SESSION A - GAMES (Jesuit Hall) Chair: Peter Widmayer |
| 14:30 – 15:00 | Congestion Games with Player-Specific Constants Marios Mavronicolas, Igal Milchtaich, Burkhard Monien and Karsten Tiemann |
| 15:00 – 15:30 | Finding Patterns In Given Intervals Maxime Crochemore, Costas Iliopoulos and M Sohel Rahman |
| 15:30 – 16:00 | The Power of Two Prices: Beyond Cross-Monotonicity Yvonne Bleischwitz, Burkhard Monien, Florian Schoppmann and Karsten Tiemann |
| 16:00 – 16:30 | Coffee Break |
| 16:30 – 17:30 | SESSION A - ALGEBRA + STRINGS (Jesuit Hall) Chair: Peter Widmayer |
| 16:30 – 17:00 | Semisimple Algebras of Almost Minimal Rank over the Reals Markus Bläser and Andreas Meyer |
| 17:00 – 17:30 | Structural Analysis of Gapped Motifs of a String Esko Ukkonen |
Friday August 31, 2007
| 9:00 – 9:55 | KEYNOTE (Jesuit Hall) Ludek Kucera |
| 9:00 – 9:55 | How To Be Fickle Vašek Chvátal |
| 9:55 – 10:00 | Short Break |
| 10:00 – 11:00 | SESSION A - NETWORKS (Jesuit Hall) Chair: Paul Spirakis |
| 10:00 – 10:30 | Communication in Networks with Random Dependent Faults Evangelos Kranakis, Michel Paquette and Andrzej Pelc |
| 10:30 – 11:00 | Optimal Gossiping in Directed Geometric Radio Networks in Presence of Dynamical Faults Andrea Clementi, Angelo Monti, Francesco Pasquale and Riccardo Silvestri |
| 11:00 – 11:30 | Coffee Break |
| 11:30 – 13:00 | SESSION A - ALGORITHMS (Jesuit Hall) Chair: Paul Spirakis |
| 11:30 – 12:00 | Online and Offline Access to Short Lists Torben Hagerup |
| 12:00 – 12:30 | Optimal Randomized Comparison Based Algorithms for Collision Riko Jacob |
| 12:30 – 13:00 | Randomized and Approximation Algorithms for Blue-Red Matching Christos Nomikos, Aris Pagourtzis and Stathis Zachos |
| 13:00 – 14.30 | Lunch Break |
| 14:30 – 16:00 | SESSION A - WORDS AND GRAPHS (Jesuit Hall) Chair: Ludek Kucera |
| 14:30 – 15:00 | Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation Klaus Meer and Martin Ziegler |
| 15:00 – 15:30 | Finding Paths Between Graph Colourings: PSPACE-completeness and Superpolynomial Distances Paul Bonsma and Luis Cereceda |
| 15:30 – 16:00 | Shuffle Expressions and Words with Nested Data Mikolaj Bojanczyk and Henrik Bjorklund |
| 16:00 – 16:15 | Closing |