Conference Program
Monday Tuesday Wednesday Thursday Friday
| Monday | |
| 9.00 | Opening |
| 9.10 | Invited talk A Case Study of Genome Evolution: From Continuous to Discrete Time Model Jerzy Tiuryn, Ryszard Rudnicki, Damian Wojtowicz |
| 10.00 | Coffee break |
| Section A (Graph Algorithms) | |
| 10.30 | Equitable Colorings of Bounded Treewidth Graphs
Hans L. Bodlaender, Fedor V. Fomin |
| 10.55 | The Bidimensional Theory of Bounded-Genus Graphs
Erik D. Demaine, Mohammad Taghi Hajiaghayi and Dimitrios M. Thilikos |
| 11.20 | Parallel Knock-out Schemes in Networks
Hajo Broersma, Fedor V. Fomin, Gerhard J. Woeginger |
| 11.45 | On-line Algorithms for Disk Graphs
Ioannis Caragiannis, Aleksei Fishkin, Christos Kaklamanis, Evi Papaioannou |
| Section B (Approximations) | |
| 10.30 | Protein Folding in the HP Model on Grid Lattices with Diagonals
Hans-Joachim Bockenhauer, Dirk Bongartz |
| 10.55 | Optimization, Games, and Quantified Constraint Satisfaction
Hubie Chen, Martin Pal |
| 11.20 | Approximating Boolean Functions by OBDDs
Andre Gronemeier |
| 11.45 | On Approximation Hardness of the Minimum 2SAT-DELETION Problem
Miroslav Chlebik, Janka Chlebikova |
| 12.10 | Lunch |
| 14.00 | Invited talk Multicoloring: Problems and Techniques Magnus M. Halldorsson, Guy Kortsarz |
| 15.00 | Coffee break |
| Section A (Graphs and Complexity) | |
| 15.30 | Group Coloring and List Group Coloring are Pi2P-complete
Daniel Kral', Pavel Nejedly |
| 15.55 | Complexity Results in Graph Reconstruction
Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw Radziszowski, Rahul Tripathi |
| 16.20 | Generating Paths and Cuts in Multi-pole (Di)Graphs
Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino |
| 16.45 | Packing Directed Cycles Efficiently
Zeev Nutov, Raphael Yuster |
| Section B (Circuits) | |
| 15.30 | The Complexity of Membership Problems for Circuits over Sets of Integers
Stephen D. Travers, |
| 15.55 | Some Meet-in-the-Middle Circuit Lower Bounds
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen |
| 16.20 | The Enumerability of P Collapses P to NC
Alina Beygelzimer, Mitsunori Ogihara |
| 16.45 | On NC1 Boolean Circuit Composition of Non-Interactive Perfect Zero-Knowledge
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano |
| Monday Tuesday Wednesday Thursday Friday | |
| Tuesday | |
| 9.00 | Invited talk Some Recent Progress in Algorithmic Randomness Rod Downey |
| 10.00 | Coffee break |
| Section A (General Complexity) | |
| 10.30 | All Superlinear Inverse Schemes are coNP-Hard
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel |
| 10.55 | The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups
Gustav Nordh |
| 11.20 | Generation Problems
Elmar Bohler, Christian Glasser, Bernhard Schwarz, Klaus Wagner |
| 11.45 | One Query Reducibilities between Partial Information Classes
Sebastian Bab, Arfst Nickelsen |
| Section B (Automata) | |
| 10.30 | A New Dimension Sensitive Property for Cellular Automata
Vincent Bernardi, Bruno Durand, Enrico Formenti, Jarkko Kari |
| 10.55 | Captive Cellular Automata
Guillaume Theyssier |
| 11.20 | Simulating 3D Cellular Automata with 2D Cellular Automata
Victor Poupet |
| 11.45 | Graph Exploration by a Finite Automaton
Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, David Peleg |
| 12.10 | Lunch |
| 14.00 | Invited talk Ubiquitous Parametrization -- Invitation to Fixed-Parameter Algorithms Rolf Niedermeier |
| 15.00 | Coffee break |
| Section A (Kolmogorov and Parametrized Complexity) | |
| 15.30 | On Polynomially Time Bounded Symmetry of Information
Troy Lee, Andrei Romashchenko |
| 15.55 | Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets
John M. Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo |
| 16.20 | A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs
Henning Fernau, David Juedes |
| 16.45 | Polynomial Time Approximation Schemes and Parameterized Complexity
Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia |
| Section B (Semantics) | |
| 15.30 | Epistemic Foundation of the Well-Founded Semantics over Bilattices
Yann Loyer, Umberto Straccia |
| 15.55 | Structural Model Checking for Communicating Hierarchical Machines
Ruggero Lanotte, Andrea Maggiolo-Schettini, Adriano Peron |
| 16.20 | Compositional Verification: Decidability Issues Using Graph Substitutions
Olivier Ly |
| 16.45 | Event Structures for Resolvable Conflict
Rob van Glabbeek, Gordon Plotkin |
| Monday Tuesday Wednesday Thursday Friday | |
| Wednesday | |
| 9.00 | Invited Talk PRAM-On-Chip: A Quest for Not-So-Obvious Non-Obviousness Uzi Vishkin |
| 10.00 | Coffee break |
| 10.30 | Invited Talk Theory and Applied Computing: Observations and Anecdotes Matthew Brand, Sarah Frisken, Neal Lesh, Joe Marks, Daniel Nikovski, Ron Perry, Jonathan Yedidia |
| 11.30 | Lunch |
| Monday Tuesday Wednesday Thursday Friday | |
| Thursday | |
| 9.00 | Invited talk Boxed Ambients with Communication Interfaces Eduardo Bonelli, Adriana Compagnoni, Mariangiola Dezani-Ciancaglini, Pablo Garralda |
| 10.00 | Coffee break |
| Section A (Scheduling) | |
| 10.30 | Optimal Preemptive Scheduling for General Target Functions
Leah Epstein, Tamir Tassa |
| 10.55 | The Price of Anarchy for Polynomial Social Cost
Martin Gairing, Thomas Lucking, Marios Mavronicolas, Burkhard Monien |
| 11.20 | Agent-Based Information Handling in Large Networks
Robert Elsasser, Ulf Lorenz, Thomas Sauerwald |
| 11.45 | Approximating Earliest Arrival Flows with Flow-Dependent Transit Times
Nadine Baumann, Ekkehard Kohler |
| Section B (Algebraic Theory of Languages) | |
| 10.30 | A Hierarchy of Irreducible Sofic Shifts
Marie-Pierre Beal, Francesca Fiorenzi, Dominique Perrin |
| 10.55 | Membership and Reachability Problems for Row-Monomial Transformations
Alexei Lisitsa, Igor Potapov |
| 11.20 | On Pseudovarieties of Semiring Homomorphisms
Libor Polak |
| 11.45 | An Algebraic Generalization of omega-Regular Languages
Zoltan Esik, Werner Kuich |
| 12.10 | Lunch |
| 14.00 | Invited talk Algebraic Recognizability of Languages Pascal Weil |
| 15.00 | Coffee break |
| Section A (Games) | |
| 15.30 | A Protocol for Serializing Unique Strategies
Marcel Crasmaru, Christian Glasser, Kenneth W. Regan, Samik Sengupta |
| 15.55 | A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games
Henrik Bjorklund, Sven Sandberg, Sergei Vorobyov |
| 16.20 | When Can You Play Positionally?
Hugo Gimbert, Wieslaw Zielonka |
| Section B (Languages) | |
| 15.30 | The Dual of Concatenation
Alexander Okhotin |
| 15.55 | Computational Aspects of Disjunctive Sequences
Klaus Ambos-Spies, Edgar Busse |
| 16.20 | Decidability of Trajectory-Based Equations
Michael Domaratzki, Kai Salomaa |
| Monday Tuesday Wednesday Thursday Friday | |
| Friday | |
| 9.00 | Invited talk Geometric Optimization and Unique Sink Orientations of Cubes Emo Welzl |
| 10.00 | Coffee break |
| Section A (Geometry) | |
| 10.30 | Efficient View Point Selection for Silhouettes of Convex Polyhedra
Therese Biedl, Masud Hasan, Alejandro Lopez-Ortiz |
| 10.55 | Angles and Lengths in Reconfigurations of Polygons and Polyhedra
Therese Biedl, Anna Lubiw, Michael J. Spriggs |
| 11.20 | Improved Bounds and Schemes for the Declustering Problem
Benjamin Doerr, Nils Hebbinghaus, Soren Werth |
| 11.45 | Crossing Number is Hard for Cubic Graphs
Petr Hlineny |
| Section B (Languages and Complexity) | |
| 10.30 | A Reducibility for the Dot-Depth Hierarchy
Victor L. Selivanov, Klaus W. Wagner |
| 10.55 | Sublogarithmic Ambiguity
Klaus Wich |
| 11.20 | An Elementary Proof for the Non-parametrizability of the Equation xyz=zvx
Elena Petre |
| 11.45 | A Generalization of Repetition Threshold
Lucian Ilie, Pascal Ochem, Jeffrey Shallit |
| 12.10 | Lunch |
| 14.00 | Invited talk Congestion Games and Coordination Mechanisms Elias Koutsoupias |
| 15.00 | Coffee break |
| Section A (Quantum Computing) | |
| 15.30 | An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation
Harumichi Nishimura, Tomoyuki Yamakami |
| 15.55 | Universal Test for Quantum One-Way Permutations
Akinori Kawachi, Hirotada Kobayashi, Takeshi Koshiba, Raymond H. Putra |
| 16.20 | A Common Algebraic Description for Probabilistic and Quantum Computations
Martin Beaudry, Jose M. Fernandez, Markus Holzer |
| Section B (XML) | |
| 15.30 | Extraction and Implication of Path Constraints
Anne-Cecile Caron, Yves Andre, Denis Debarbieux, Yves Roos, Sophie Tison |
| 15.55 | Schema Evolution for XML: A Consistency-Preserving Approach
Beatrice Bouchou, Denio Duarte, Mirian Halfeld Ferrari Alves, Dominique Laurent, Martin A. Musicante |
| 16.20 | Complexity of Decision Problems for Simple Regular Expressions
Wim Martens, Frank Neven, Thomas Schwentick |
| 16.45 | Closing session |