MFCS 2006
31st International Symposium on
Mathematical Foundations of Computer Science
August 28 - September 1, 2006

The invited talks are 50min, contributed 25min long, including discussion. Dataprojector, PC (MS Windows 2000, MS Office 2000, Acrobat Reader, and whiteboard will be available in the lecture rooms. The conference hotel promised to provide wireless internet access.



9:00–9:50 Martin Grohe The structure of tractable constraint satisfaction problems (Invited Talk)

10:00–11:15 SESSION 1

Richard Beigel, William Gasarch and James Glenn The Multiparty Communication Complexity of Exact-T

Andre Gronemeier NOF-Multiparty Information Complexity Bounds for Pointer Jumping

Francois Le Gall Quantum Weakly Nondeterministic Communication Complexity

11:45–13:00 SESSION 2A

Anna Gal and Vladimir Trifonov On the Correlation Between Parity and Modular Polynomials

Kazuo Iwama and Hiroki Morizumi Reductions for Monotone Boolean Circuits

Rene Peralta and Joan Boyar Concrete multiplicative complexity of symmetric functions

11:45–13:00 SESSION 2B

Sasanka Roy, Arindam Karmakar, Sandip Das and Subhas C. Nandy Constrained Minimum Enclosing Circle with Center on a Query Line Segment

Wael El-Oraiby and Dominique Schmitt $k$-sets of convex inclusion chains of planar point sets

Oswin Aichholzer, Clemens Huemer, Sarah Kappes, Bettina Speckmann and Csaba D. Toth On Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-Triangles

15:00–15:50 Andrzej Pelc Oracles: A new paradigm for network algorithms (Invited Talk)

16:15–17:30 SESSION 3

Martin Kutrib and Andreas Malcher Fast Iterative Arrays with Restricted Inter-Cell Communication: Constructions and Decidability

Guillaume Theyssier, Victor Poupet and Laurent Boyer On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures

Pablo Arrighi Algebraic characterizations of unitary one dimensional quantum cellular automata


9:00–9:50 Cyril Gavoille Distributed Data Structures: A Survey on Informative Labeling Schemes( Invited talk)

10:00–11:15 SESSION 1

F. Blanchet-Sadri, D. Dakota Blair and Rebeca V. Lewis Equations on Partial Words

Alessandra Savelli and Jean Berstel Crochemore factorization of Sturmian and other infinite words

Arturo Carpi On the repetition threshold for large alphabets

11:45–13:00 SESSION 2

A.N. Trahtman An efficient algorithm finds noticeable trends and examples concerning the Cerny conjecture

Alessandra Cherubini, Pawel Gawrychowski, Andrzej Kisielewicz and Brunetto Piochi A Combinatorial Approach to Collapsing Words

Volker Diekert, Markus Lohrey and Alexander Miller Partially commutative inverse monoids

15:00–16:15 SESSION 3

Peter Jonsson and Gustav Nordh Generalised Integer Programming Based on Logically Defined Relations

Alexander Kostin A Reachability Algorithm for General Petri Nets Based on Transition Invariants

Slawomir Lasota and Wojciech Rytter Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes

16:45–18:00 SESSION 4A

Martin Hoefer Non-cooperative Tree Creation

Angelo Fanelli, Michele Flammini, Giovanna Melideo and Luca Moscardelli Multicast Transmissions in Non-Cooperative Networks with a Limited Number of Selfish Moves

Marios Mavronicolas, Loizos Michael, Vicky Papadopoulou, Anna Philippou and Paul Spirakis The Price of Defense

16:45–18:00 SESSION 4B

Yury Lifshits and Markus Lohrey Querying and Embedding Compressed Texts

Sorin Constantinescu and Lucian Ilie The Lempel--Ziv complexity of fixed points of morphisms

Maria Lopez-Valdes Lempel-Ziv Dimension for Lempel-Ziv Compression


9:00–9:50 Ming LI From Three Ideas in TCS to Three Applications in Bioinformatics (Invited Talk)

10:00–11:40 SESSION 1A

Linh Anh Nguyen The Data Complexity of MDatalog in Basic Modal Logics

Sergey Goncharov, Lutz Schrder and Till Mossakowski Completeness of Global Evaluation Logic

Giuseppe Persiano and Ivan Visconti On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model

Yoram Hirshfeld and Alexander Rabinovich An Expressive Temporal Logic for Real Time

10:00–11:40 SESSION 1B

Damian Wojtowicz and Jerzy Tiuryn On genome evolution with innovation

Marcin Kik Sorting Long Sequence in a Single Hop Radio Network

Miroslaw Dynia, Jaroslaw Kutylowski, Friedhelm Meyer auf der Heide and Christian Schindelhauer Smart Robot Teams Exploring Sparse Trees

Adele Rescigno and Luisa Gargano Optimally Fast Data Gathering in Sensor Networks


9:00-9:50 Martin Odersky A Core Calculus for Scala Type Checking (Invited Talk)

10:00–11:15 SESSION 1

Rodrigo Leao and Valmir Barbosa Minimal Chordal Sense of Direction and Circulant Graphs

Jianer Chen, Iyad kanj and Ge Xia Improved Parameterized Upper Bounds for Vertex Cover

Ulrik Brandes and Juergen Lerner Coloring Random 3-Colorable Graphs with Non-Uniform Edge Probabilities

11:45–13:00 SESSION 2

Johanne Cohen, Fedor Fomin, Pinar Heggernes, Dieter Kratsch and Gregory Kucherov Optimal Linear Arrangement of Interval Graphs

Robert Elsaesser Toward the Eigenvalue Power Law

Arnaud Carayol and Didier Caucal The Kleene equality for graphs

15:00–15:50 Dexter Kozen On the Representation of Kleene Algebras with Tests (Invited Talk)

16:15–17:30 SESSION 3A

Pascal Koiran and Sylvain Prifel Valiant's model: from exponential sums to exponential products

Xiaoyang Gu and Jack H. Lutz Dimension Characterizations of Complexity Classes

Guillaume Malod and Natacha Portier Characterizing Valiant's algebraic complexity classes

16:15–17:30 SESSION 3B

Christopher Homan and Lane A. Hemaspaandra Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners

Vikraman Arvind and Piyush P Kurur A Polynomial Time Nilpotence Test for Galois Groups and Related Results

Qi Cheng On comparing sums of square roots of small integers


9:00–9:50 Herman Geuvers From Deduction Graphs to Proof Nets: Boxes and Sharing in the Graphical Presentation of Deductions (Invited Talk)

10:00–11:15 SESSION 1

Holger Spakowski and Rahul Tripathi Hierarchical Unambiguity

Beat Gfeller, Leon Peeters, Birgitta Weber and Peter Widmayer Online Single Machine Batch Scheduling

Norbert Dojer Learning Bayesian networks does not have to be NP-hard

11:45–13:00 SESSION 2A

Fredrik Kuivinen Approximability of Bounded Occurrence Max Ones

Refael Hassin, Jerome Monnot and Danny Segev Approximation Algorithms and Hardness Results for Labeled Connectivity Problems

Lyudmil Aleksandrov, Hristo N. Djidjev, Hua Guo, Anil Maheshwari, Doron Nussbaum and Jorg Sack Approximate Shortest Path Queries on Weighted Polyhedral Surfaces

11:45–13:00 SESSION 2B

Viliam Geffert Magic Numbers in the State Hierarchy of Finite Automata

Michael Domaratzki and Kai Salomaa Lower Bounds for the Transition Complexity of NFAs

Cyril Allauzen and Mehryar Mohri A Unified Construction of the Glushkov, Follow, and Antimirov Automata

15:00–16:15 SESSION 3

Tomasz Jurdzinski Probabilistic Length-Reducing Automata

Aris Pagourtzis and Stathis Zachos The Complexity of Counting Functions with Easy Decision Version

Ondrej Klima, Benoit Larose and Pascal Tesson Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture

16:45–18:00 SESSION 4

Lance Fortnow and Mitsunori Ogihara Very Sparse Leaf Languages

Christian Glasser and Stephen David Travers Machines that can Output Empty Words

Petr Hlineny On Matroid Representability and Minor Problems

Social events: