| 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 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 |
|
|
|
|
|
|
| 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. 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 |
|
|
|
|
|
|
| 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 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 |
|
|
|
|
|
|
| Thursday |
|
|
|
| 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 |
|
|
|
|
|
|
| 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 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 |
