Monday 



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 ExactT 

Andre Gronemeier 
NOFMultiparty 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 ElOraiby 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 PseudoTriangles 



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 InterCell 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 






Tuesday 



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



10:00–11:15 
SESSION 1 


F. BlanchetSadri, 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 ContextFree Processes 



16:45–18:00 
SESSION 4A 


Martin Hoefer 
Noncooperative Tree Creation 

Angelo Fanelli, Michele Flammini, Giovanna Melideo and Luca Moscardelli 
Multicast Transmissions in NonCooperative 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 LempelZiv complexity of fixed points of morphisms 

Maria LopezValdes 
LempelZiv Dimension for LempelZiv Compression 






Wednesday 



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 NonInteractive ZeroKnowledge 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 






Thursday 



9:009: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 3Colorable Graphs with NonUniform 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 DodgsonElection 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 






Friday 



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 NPhard 



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 LengthReducing 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 