Wednesday, June 16 |
| 08:00 |
- 09:00 |
Registration |
|
|
| 09:00 |
- 09:30 |
Welcome and Opening |
|
|
| 09:30 |
- 10:30 |
Opening Lecture |
Alexander Razborov |
Complexity of Propositional
Proofs |
| 10:30 |
- 11:00 |
Coffee Break |
|
|
| 11:00 |
- 11:30 |
|
Daniel Raible and
Henning Fernau |
A Faster Exact Algorithm
for the Directed Maximum Leaf Spanning Tree Problem |
| 11:30 |
- 12:00 |
|
Maurice Jansen and
Jayalal Sarma M.N. |
Balancing Bounded
Treewidth Circuits |
| 12:00 |
- 12:30 |
|
Ling-Ju Hung and
Ton Kloks |
Classifying Rankwidth
k-DH-Graphs |
| 12:30 |
- 14:30 |
Lunch |
|
|
| 14:30 |
- 15:30 |
Invited Talk |
Juraj Hromkovic |
Algorithmics –
Is There Hope for a Unified Theory? |
| 15:30 |
- 16:00 |
Coffee Break |
|
|
| 16:00 |
- 16:30 |
|
A.N. Trahtman |
A Partially Synchronizing
Coloring |
| 16:30 |
- 17:00 |
|
Matthew Johnson,
Viresh Patel, Daniel Paulusma and Théophile Trunck |
Obtaining Online
Ecological Colourings by Generalizing First-Fit |
| 17:00 |
- 17:30 |
|
Nick Gravin |
Time optimal d-list
colouring of a graph |
| 19:00 |
|
Welcome Party |
|
|
Thursday, June 17 |
| 09:30 |
- 10:30 |
Invited Talk |
Fedor Fomin |
Kernelization |
| 10:30 |
- 11:00 |
Coffee Break |
|
|
| 11:00 |
- 11:30 |
|
James Gate and Iain
A. Stewart |
Frameworks for Logically
Classifying Polynomial-time Optimisation Problems |
| 11:30 |
- 12:00 |
|
Vladimir N. Krupski |
Symbolic models for
single-conclusion proof logics |
| 12:00 |
- 12:30 |
|
Junhua Yu |
Prehistoric Phenomena
and Self-referentiality |
| 12:30 |
- 14:30 |
Lunch |
|
|
| 14:30 |
- 15:30 |
Invited Talk |
Miklos Santha |
Quantization of random
walks: Search algorithms and hitting time |
| 15:30 |
- 16:00 |
Coffee Break |
|
|
| 16:00 |
- 16:30 |
|
Dmitry Itsykson |
Lower bound on average-case
complexity of inversion of Goldreich's function by drunken backtracking
algorithms |
| 16:30 |
- 17:00 |
|
Janusz Brzozowski,
Galina Jirásková and Chenglong Zou |
Quotient Complexity
of Closed Languages |
| 17:00 |
- 17:30 |
|
Pavel V. Martyugin |
Complexity of problems
concerning carefully synchronizing words for PFA and directing words
for NFA |
| 17:30 |
- 18:00 |
|
Anahí Gajardo and
Pierre Guillon |
Zigzags in Turing
Machines |
| 19:00 |
- 21:00 |
Social Program |
|
|
Friday, June 18 |
| 09:30 |
- 10:30 |
Invited Talk |
Uwe Schöning |
Comparing Two Stochastic
Local Search Algorithms for Constraint Satisfaction Problems |
| 10:30 |
- 11:00 |
Coffee Break |
|
|
| 11:00 |
- 11:30 |
|
Renat A. Gimadeev
and Mikhail N. Vyalyi |
Identical relations
in symmetric groups and separating words with reversible automata |
| 11:30 |
- 12:00 |
|
Arseny M. Shur |
Growth of power-free
languages over large alphabets |
| 12:00 |
- 12:30 |
|
Victor Y. Pan, Gouliang
Qian and AI-Long Zheng |
On the Power of Randomized
Multiplicative Preprocessing |
| 12:30 |
- 14:30 |
Lunch |
|
|
| 14:30 |
- 15:30 |
Invited Talk |
Susanne Albers |
Algorithms for Energy
Management |
| 15:30 |
- 16:00 |
Coffee Break |
|
|
| 16:00 |
- 16:30 |
|
Nicolas Bourgeois,
Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, Vangelis Th.
Paschos and Olivier Pottié |
The max quasi-independent
set problem |
| 16:30 |
- 17:00 |
|
Gerold Jäger and
Weixiong Zhang |
A SAT based effective
algorithm for the directed Hamiltonian cycle problem |
| 17:00 |
- 17:30 |
|
Pawel Gawrychowski,
Artur Jez and Lukasz Jez |
Validating the Knuth-Morris-Pratt
failure function, fast and online |
| 17:30 |
- 18:15 |
Business Meeting |
|
|
Saturday, June 19 |
| 09:30 |
- 10:30 |
Invited Talk |
Prabhakar Raghavan |
The quantitative
analysis of user behavior online - data, models and algorithms |
| 10:30 |
- 11:00 |
Coffee Break |
|
|
| 11:00 |
- 11:30 |
|
Benedikt Bollig and
Loïc Hélouët |
Realizability of
Dynamic MSC Languages |
| 11:30 |
- 12:00 |
|
Nazim Benaissa and
Dominique Méry |
Proof-based Design
of Security Protocols |
| 12:00 |
- 12:30 |
|
Thomas Brihaye, Véronique
Bruyère and Julie De Pril |
Equilibria in quantitative
reachability games |
| 12:30 |
- 14:30 |
Lunch |
|
|
| 14:30 |
|
Social Program |
|
|
| 19:00 |
|
Conference Dinner |
|
|
Sunday, June 20 |
| 09:30 |
- 10:00 |
|
Mikhail V. Berlinkov |
Approximating the
minimum length of synchronizing words is hard |
| 10:00 |
- 10:30 |
|
Nikolay Vereshchagin |
An Encoding Invariant
Version of Polynomial Time Computable Distributions |
| 10:30 |
- 11:00 |
Coffee Break |
|
|
| 11:00 |
- 11:30 |
|
Elena Kalinina |
Prefix-free and Prefix-correct
Complexities with Compound Conditions |
| 11:30 |
- 12:00 |
|
Pavel Karpovich |
Monotone complexity
of a pair |
| 12:00 |
- 12:30 |
|
Nathalie Aubrun and
Marie-Pierre Béal |
Sofic and almost
of finite type tree-shifts |
| 12:30 |
- 14:30 |
Lunch |
|
|
| 14:30 |
- 15:30 |
Invited Talk |
Richard Jozsa |
Classical Simulation
and Complexity of Quantum Computations |
| 15:30 |
- 16:00 |
Coffee Break |
|
|
| 16:00 |
- 16:30 |
|
Olivier Carton |
Right sequential
functions on infinite words |
| 16:30 |
- 17:00 |
|
Bernhard Heinemann |
The Cantor Space
as a Generic Model of Topologically Presented Knowledge |
| 17:00 |
- 17:30 |
|
Valery Plisko |
Transfinite Sequences
of Constructive Predicate Logics |
| 17:30 |
|
End of Conference |
|
|
