|
Program |
| Sunday, August 24 | ||
| 15:00 | 19:00 | Registration |
| Monday, August 25 | ||
| 7:00 | 9:00 | Registration |
| Queries | ||
| 9:00 | 9:30 |
Complexity of Data Tree Patterns over XML Documents Claire David |
| 9:30 | 10:00 |
Optimizing Conjunctive Queries over Trees using Schema Information Henrik Björklund, Wim Martens and Thomas Schwentick |
| 10:00 | 10:30 |
Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise Bodo Manthey and Till Tantau |
| 10:30 | 11:00 | Coffee Break |
| Cryptography | ||
| 11:00 | 11:30 |
Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control Gábor Erdélyi, Markus Nowak and Jörg Rothe |
| 11:30 | 12:00 |
Step-out Ring Signatures Marek Klonowski, £ukasz Krzywiecki, Miros³aw Kuty³owski and Anna Lauks |
| 12:00 | 12:10 | Cigarette Break |
| Invited Lecture by Piotr Sankowski | ||
| 12:10 | 13:10 |
Algebraic Graph Algorithms Piotr Sankowski |
| 13:10 - 15:30 free time 13:10 - 15:30 | ||
| Coloring | ||
| 15:30 | 16:00 |
A Note on k-colourability of P_5-free Graphs Chinh T. Hoáng, Marcin Kamiñski, Vadim Lozin, Joe Sawada and Xiao Shu |
| 16:00 | 16:30 |
Colouring Random Empire Trees Andrew R. McGrae and Michele Zito |
| 16:30 | 17:00 | Coffee Break |
| Languages I | ||
| 17:00 | 17:30 |
The Height of Factorization Forests Manfred Kufleitner |
| 17:30 | 18:00 |
Succinctness of Regular Expressions with Interleaving, Intersection and Counting Wouter Gelade |
|
18:10 welcome party 18:10 | ||
| Tuesday, August 26 | ||
| Logic I | ||
| 9:00 | 9:30 |
A Complete Axiomatic System for a Process-Based Spatial Logic Radu Mardare and Alberto Policriti |
| 9:30 | 10:00 |
Complexity and Asymptotic Density of Boolean Functions over Implication Hervé Fournier, Daniele Gardy, Antoine Genitrini and Bernhard Gittenberger |
| 10:00 | 10:30 |
Monadic Second Order Logic on Graphs with Local Cardinality Constraints Stefan Szeider |
| 10:30 | 11:00 | Coffee Break |
| Models | ||
| 11:00 | 11:30 |
Directed Percolation Arising in Stochastic Cellular Automata Analysis Damien Regnault |
| 11:30 | 12:00 |
Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems Michael Elberfeld and Till Tantau |
| 12:00 | 12:10 | Cigarette Break |
| Invited Lecture by Jean-Éric Pin | ||
| 12:10 | 13:10 |
A Robust Class of Regular Languages Antonio Cano Gómez and Jean-Éric Pin |
| 13:10 - 15:30 free time 13:10 - 15:30 | ||
| Games I | ||
| 15:30 | 16:00 |
When Ignorance Helps: Graphical Multicast Cost Sharing Games Vittorio Bilo, Angelo Fanelli, Michele Flammini and Luca Moscardelli |
| 16:00 | 16:30 |
Voronoi Games on Cycle Graphs Marios Mavronicolas, Burkhard Monien, Vicky G. Papadopoulou and Florian Schoppmann |
| 16:30 | 17:00 | Coffee Break |
| Automata and Machines I | ||
| 17:00 | 17:30 |
Reversal-Bounded Counter Machines Revisited Alain Finkel and Arnaud Sangnier |
| 17:30 | 18:00 |
On the Decidability of Bounded Valuedness for Transducers Jacques Sakarovitch and Rodrigo de Souza |
|
18:30 Torunian gingerbreads in Copernicus House - Group 1 | ||
| Wednesday, August 27 | ||
| Medley | ||
| 9:00 | 9:30 |
On the Shortest Linear Straight-line Program for Computing Linear Forms Joan Boyar, Philip Matthews and René Peralta |
| 9:30 | 10:00 |
Clustering with Partial Information Hans L. Bodlaender, Michael R. Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos and Frances A. Rosamond |
| 10:00 | 10:30 |
A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach Daniel Raible and Henning Fernau |
| 10:30 | 11:00 | Coffee Break |
| Logic II | ||
| 11:00 | 11:30 |
From Lambda Calculus to Universal Algebra and Back Giulio Manzonetto and Antonino Salibra |
| 11:30 | 12:00 |
Short Proofs of Strong Normalization Aleksander Wojdyga |
| 12:00 | 12:10 | Cigarette Break |
| Invited Lecture by Ursula Goltz | ||
| 12:10 | 13:10 |
On Synchronous and Asynchronous Interaction in Distributed Systems Rob van Glabbeek, Ursula Goltz and Jens-Wolfhard Schicke |
| 13:10 - 15:30 free time 13:10 - 15:30 | ||
| Automata and Machines II | ||
| 15:30 | 16:00 |
Nilpotency and Limit Sets of Cellular Automata Pierre Guillon and Gaétan Richard |
| 16:00 | 16:30 |
Periodicity and Immortality in Reversible Computing Jarkko Kari and Nicolas Ollinger |
| 16:30 | 17:00 | Coffee Break |
| Games II | ||
| 17:00 | 17:30 |
Positional Strategies for Higher-Order Pushdown Parity Games Arnaud Carayol and Michaela Slaats |
| 17:30 | 18:00 |
Question/Answer Games on Towers and Pyramids Sarmad Abbasi and Numan Sheikh |
|
18:30 Torunian gingerbreads in Copernicus House - Group 2 | ||
| Thursday, August 28 | ||
| Approximation | ||
| 9:00 | 9:30 |
A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem Ioannis Caragiannis and Gianpiero Monaco |
| 9:30 | 10:00 |
Approximating Independent Set and Coloring in Random Uniform Hypergraphs Kai Plociennik |
| 10:00 | 10:30 |
A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs Feodor F. Dragan, Fedor V. Fomin and Petr A. Golovach |
| 10:30 | 11:00 | Coffee Break |
| Circuits | ||
| 11:00 | 11:30 |
Lower Bounds for Syntactically Multilinear Algebraic Branching Programs Maurice J. Jansen |
| 11:30 | 12:00 |
Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae Meena Mahajan and B. V. Raghavendra Rao |
| 12:00 | 12:10 | Cigarette Break |
| Invited Lecture by Yuri Gurevich | ||
| 12:10 | 13:10 |
One Useful Logic That Defines Its Own Truth Andreas Blass and Yuri Gurevich |
| 13:10 - 15:30 free time 13:10 - 15:30 | ||
| Around NP I | ||
| 15:30 | 16:00 |
Computing Sharp 2-Factors in Claw-Free Graphs Hajo Broersma and Daniël Paulusma |
| 16:00 | 16:30 |
Reoptimization of the Metric Deadline TSP Hans-Joachim Böckenhauer and Dennis Komm |
| 16:30 | 17:00 | Coffee Break |
| Languages II | ||
| 17:00 | 17:30 |
Regional Languages and Tiling: a Unifying Approach to Picture Grammars Alessandra Cherubini, Stefano Crespi Reghizzi and Matteo Pradella |
| 17:30 | 18:00 |
A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems Emilie Charlier and Michel Rigo |
|
19:00 outdoor grill party 19:00 | ||
| Friday, August 29 | ||
| Geometry | ||
| 9:00 | 9:30 |
Resolution Width and Cutting Plane Rank are Incomparable Mark Rhodes |
| 9:30 | 10:00 |
Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations Christian Hundt and Maciej Li¶kiewicz |
| 10:00 | 10:30 |
Flip Algorithm for Segment Triangulations Mathieu Brévilliers, Nicolas Chevallier and Dominique Schmitt |
| 10:30 | 11:00 | Coffee Break |
| Complexity | ||
| 11:00 | 11:30 |
A Random Oracle Does Not Help Extract the Mutual Information Andrei Muchnik and Andrei Romashchenko |
| 11:30 | 12:00 |
Arthur and Merlin as Oracles Venkatesan T. Chakaravarthy and Sambuddha Roy |
| 12:00 | 12:10 | Cigarette Break |
| Invited Lecture by Rastislav Královiè | ||
| 12:10 | 13:10 |
Deterministic Models of Communication Faults Rastislav Královiè and Richard Královiè |
| 13:10 - 15:30 free time 13:10 - 15:30 | ||
| Languages III | ||
| 15:30 | 16:00 |
Shortest Synchronizing Strings for Huffman Codes Marek Biskup |
| 16:00 | 16:30 |
On a Special Class of Primitive Words Elena Czeizler, Lila Kari and Shinnosuke Seki |
| 16:30 | 17:00 | Coffee Break |
| Around NP II | ||
| 17:00 | 17:30 |
The Maximum Independent Set Problem in Planar Graphs Vladimir E. Alekseev, Vadim Lozin, Dmitriy Malyshev and Martin Milaniè |
| 17:30 | 18:00 |
Iterative Compression and Exact Algorithms Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff and Saket Saurabh |
|
the end | ||