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