| Monday, June 30 | ||
| 09.15 - 09.30 | Opening - Blauwe zaal | |
| 09.30 - 10.30 | Invited speaker Jan Bergstra: Polarized process algebra and program equivalence - Blauwe zaal | |
| 10.30 - 11.00 | Coffee and tea break - Voorhof/Senaatszaal | |
| 11.00 -
12.30 |
zaal 4
Algorithms |
zaal 5
Process Algebra |
| Juraj Hromkovic, Georg
Schnitger Pushdown automata and multicounter machines, a comparison of computation mode |
Stefan Blom, Wan Fokkink,
Sumit Nain On the axiomatizability of ready traces, ready simulation and failure traces | |
| Annalisa De Bonis, Leszek Gasieniec, Ugo Vaccaro
Generalized framework for selectors with applications in optimal group testing |
Daniele Gorla, Rosario
Pugliese Resource access and mobility control with dynamic privileges acquisition | |
| Daniel Bleichenbacher, Aggelos
Kiayias, Moti Yung Decoding of interleaved Reed Solomon codes over noisy data |
Nadia Busi, Maurizio
Gabbrielli, Gianluigi Zavattaro Replication vs. recursive definitions in channel based calculi | |
| 12.30 - 14.00 | Lunch - Voorhof/Senaatszaal | |
| 14.00 -
15.30 |
zaal 4
Approximation algorithms I |
zaal 5
Languages and programming |
| Alexander Ageev, Yinyu Ye,
Jiawei Zhang Improved combinatorial approximation algorithms for the k-level facility location problem |
Davide Ancona, Sonia Fagorzi,
Eugenio Moggi, Elena Zucca Mixin modules and computational effects | |
| Markus Blaeser An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality |
Alexander Okhotin Decision problems for language equations with Boolean operations | |
| Rajiv Gandhi, Eran Halperin,
Samir Khuller, Guy Kortsarz, Aravind Srinivasan An improved approximation algorithm for vertex cover with hard capacities |
Roberto Bruni, Jose Meseguer
Generalized rewrite theories | |
| 15.30 - 16.00 | Coffee and tea break - Voorhof/Senaatszaal | |
| 16.00 -
18.00 |
zaal 4
Complexity |
zaal 5
Data structures |
| Luis Antunes, Lance Fortnow
Sophistication revisited |
Gianni Franceschini, Roberto
Grossi Optimal cache-oblivious implicit dictionaries | |
| John Hitchcock, Jack Lutz,
Elvira Mayordomo Scaled dimension and nonuniform complexity |
Anna Gal, Peter Bro Miltersen
The cell probe complexity of succinct data structures, | |
| Peter Hoyer, Michele Mosca,
Ronald de Wolf Quantum search on bounded-error inputs |
Ian Munro, Rajeev Raman,
Venkatesh Raman, Srinivasa Rao Satti Succinct representations of permutations | |
| Rahul Jain, Jaikumar
Radhakrishnan, Pranab Sen A direct sum theorem in communication complexity via message compression |
Rajeev Raman, Srinivasa Rao
Succinct dynamic dictionaries and trees | |
| 20.15 - 22.00 | Special festive evening session: Presentation of the EATCS award and the NVTI life time achievement award | |
| Tuesday, July 1 | ||
| 09.00 - 10.00 | Invited speaker Petra Mutzel: The SPQR-tree data structure in graph drawing - Blauwe zaal | |
| 10.00 - 10.30 | Coffee and tea break - Voorhof/Senaatszaal | |
| 10.30 -
12.30 |
zaal 4 Graph
algorithms |
zaal 5 Automata I
|
| Amos Korman, David Peleg
Labeling schemes for weighted dynamic trees |
Manfred Droste, Dietrich Kuske
Skew and infinitary formal power series | |
| Surender Baswana, Sandeep Sen
A simple linear time algorithm for computing a (2k-1)-Spanner of O(n^{1+1/k}) size in weighted graphs |
Juraj Hromkovic, Georg
Schnitger Nondeterminisn versus determinism for two-way finite automata: generalizations of Sipser's separation | |
| Alex Hall, Steffen Hippler,
Martin Skutella Multicommodity flows over time: efficient algorithms and complexity |
Francois Denis, Yann Esposito
Residual languages and probabilistic automata | |
| Chandra Chekuri, Marcelo
Mydlarz, Bruce Shepherd Multicommodity demand flow in a tree |
Marielle Stoelinga , Frits
Vaandrager A testing scenario for probabilistic automata | |
| 12.30 - 14.00 | Lunch - Voorhof/Senaatszaal | |
| 14.00 -
16.00 |
zaal 4 Optimization and
games |
zaal 5 Graphs and bisimulation
|
| Eyal Even-Dar, Alex Kesselman,
Yishay Mansour Convergence time to Nash equilibria |
Thierry Cachat Higher order pushdown automata, the Caucal hierarchy of graphs and parity games | |
| Rainer Feldmann, Martin
Gairing, Thomas Luecking, Burkhard Monien, Manuel Rode Nashification and the coordination ratio for a selfish routing game |
Richard Mayr
Undecidability of weak bisimulation equivalence for 1-counter processes | |
| Vipul Bansal, Aseem Agrawal, Varun Malhotra Stable marriages with multiple partners: efficient search for an optimal solution |
Massimo Merro, Francesco Zappa
Nardelli Bisimulation proof methods for mobile ambients | |
| Endre Boros, Khaled
Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino An intersection inequality for discrete distributions and related generation problems |
Arnaud Carayol, Thomas
Colcombet On equivalent representations of infinite structures | |
| 16.00 - 18.00 | Excursion to and reception at Philips High Tech Campus | |
| Wednesday, July 2 | ||
| 09.00 - 10.00 | Invited speaker Amos Fiat: Some issues regarding search, censorship, and anonymity in peer to peer networks - Blauwe zaal | |
| 10.00 - 10.30 | Coffee and tea break - Voorhof/Senaatszaal | |
| 10.30 -
12.30 |
zaal 4 Online
problems |
zaal 5 Verification |
| Arnold Schoenhage Adaptive raising strategies optimizing relative efficiency |
Gaoyan Xie, Zhe Dang, Oscar Ibarra A solvable class of quadratic Diophantine equations with applications to verification of infinite state systems | |
| Rene Sitters, Leen Stougie, Willem Paepe A competitive algorithm for the general 2-server problem |
Felix Klaedtke, Harald Ruess Monadic second-order logics with cardinalities | |
| Dimitris Fotakis On the competitive ratio for online facility location |
Orna Kupferman, Moshe Vardi Pi_2 intersected Sigma_2 equals AFMC | |
| Susanne Albers, Rob van Stee A study of integrated document and connection caching |
Tatiana Rybina, Andrei Voronkov Upper bounds for a theory of queues | |
| 12.30 - 14.00 | Lunch - Voorhof/Senaatszaal | |
| 14.00 - 15.00 | Invited speaker Doron Peled: Model checking and testing combined - Blauwe zaal | |
| 15.00 - 15.30 | Coffee and tea break - Voorhof/Senaatszaal | |
| 15.30 -
17.00 |
zaal 4 Around the internet
|
zaal 5 Temporal logic and
model checking |
| Noam Berger, Bela Bollobas,
Christian Borgs, Jennifer Chayes, Oliver Riordan Degree distribution of the FKP network model |
Jan Johannsen, Martin Lange
CTL+ is complete for double exponential time | |
| Vincent Blondel, Paul Van
Dooren Similarity matrices for pairs of graphs |
Salvatore La Torre, Margherita
Napoli, Mimmo Parente, Gennaro Parlato Hierarchical and recursive state machines with context-dependent properties | |
| Randeep Bhatia, Julia Chuzhoy,
Ari Freund, Joseph Naor Algorithmic aspects of bandwidth trading |
Philippe Schnoebelen
Oracle circuits for branching-time model checking | |
| 17.00 - 19.00 | EATCS General Assembly | |
| Thursday, July 3 | ||
| 09.00 - 10.00 | Invited speaker Moshe Vardi: Logic and automata, a match made in heaven - Blauwe zaal | |
| 10.00 - 10.30 | Coffee and tea break - Voorhof/Senaatszaal | |
| 10.30 -
12.30 |
zaal 4 Graph problems
|
zaal 5 Logic and
lambda-calculus |
| Luisa Gargano, Mikael Hammar There are spanning spiders in dense graphs (and we know how to find them) |
Cindy Eisner, Dana Fisman, John Havlicek, Anthony McIsaac,
David Van Campenhout The definition of a temporal clock operator | |
| Jiri Fiala, Daniel Paulusma The computational complexity of the role assignment problem |
Zena Ariola, Hugo Herbelin Minimal classical logic and control operators | |
| Erik Demaine, Fedor Fomin, MohammadTaghi Hajiaghayi,
Dimitrios Thilikos Fixed-parameter algorithms for the (k,r)-center in planar graphs and map graphs |
Thomas Henzinger, Ranjit Jhala, Rupak Majumdar
Counterexample guided control | |
| Jianer Chen, Iyad Kanj, Ljubomir Perkovic, Eric Sedgwick, Ge
Xia Genus characterizes the complexity of graph problems: some tight results |
Jo Hannay Axiomatic criteria for quotients and subobjects for higher-order data types | |
| 12.30 - 14.00 | Lunch - Voorhof/Senaatszaal | |
| 14.00 -
15.30 |
zaal 4 Data
structures and algorithms |
zaal 5 Types
and categories |
| Yossi Matias, Ely Porat Efficient pebbling for list traversal synopses |
Francisco Gutierrez, Blas Ruiz Expansion postponement via cut elimination in sequent calculi for pure type systems | |
| Amihood Amir, Yonatan Aumann, Richard Cole, Moshe
Lewenstein, Ely Porat Function matching: algorithms, applications, and a lower bound |
Michele Bugliesi, Silvia Crafa, Amela Prelic, Vladimiro
Sassone Secrecy in untrusted networks | |
| Juha Kärkkäinen, Peter Sanders Simple linear work suffix array construction |
Arkadev Chattopadhyay, Denis Therien Locally commutative categories | |
| 15.30 - 16.00 | Coffee and tea break - Voorhof/Senaatszaal | |
| 16.00 -
18.00 |
zaal 4
Approximation algorithms II |
zaal 5 Probabilistic
systems |
| Sanjeev Arora, Kevin Chang Approximation schemes for degree-restricted MST and red-blue separation problem |
Ernst-Erich Doberkat Semi-pullbacks and bisimulations in categories of stochastic relations | |
| Chandra Chekuri, Sudipto Guha, Joseph Naor Approximating Steiner k-cuts |
Alexander Rabinovich Quantitative analysis of probabilistic lossy channel systems | |
| Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani MAX k-CUT and approximating the chromatic number of random graphs |
Luca de Alfaro, Thomas A. Henzinger, Rupak Majumdar Discounting the future in systems theory | |
| Michael Elkin, Guy Kortsarz Approximation algorithm for the directed telephone multicast problem |
Luca de Alfaro, Marco Faella Information flow in concurrent games | |
| 18.00 - 23.00 | Combined social event and conference dinner at the Efteling | |
| Friday, July 4 | ||
| 09.00 - 10.00 | Invited speaker Anne Condon: Problems in RNA secondary structure prediction and design - Blauwe zaal | |
| 10.00 - 10.30 | Coffee and tea break - Voorhof/Senaatszaal | |
| 10.30 -
12.30 |
zaal 4 Sampling and
randomness |
zaal 5 Scheduling |
| Satoshi Ikeda, Izumi Izumi Kubo, Norihiro Okumoto, Masafumi
Yamashita Impact of local topological information on random walks on finite graphs |
Pilu Crescenzi, Giorgio Gambosi, Gaia Nicosia, Paolo Penna,
Walter Unger On-line load balancing made simple: greedy strikes back | |
| Jens Jaegerskuepper Analysis of a simple evolutionary algorithm for minimization in Euclidean spaces |
Seffi Naor, Hadas Shachnai, Tami Tamir Real-time scheduling with a budget | |
| Dominique Poulalhon, Gilles Schaeffer Optimal coding and sampling of triangulations |
Brian Dean, Michel Goemans Improved approximation algorithms for minimum-space advertisement scheduling | |
| Manuel Bodirsky, Clemens Gröpl, Mihyun Kang Generating labeled planar graphs uniformly at random |
Baruch Awerbuch, Andre Brinkmann, Christian Scheideler
Anycasting in adversarial systems: routing and admission control | |
| 12.30 - 14.00 | Lunch - Voorhof/Senaatszaal | |
| 14.00 -
15.00 |
zaal 4
Geometric problems |
zaal 5 Automata
2 |
| Sergei Bespamyatnikh, Michael Segal
Dynamic algorithms for approximating interdistances |
Geraud Senizergues The equivalence problem for t-turn DPDA is co-NP | |
| Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, Nicola
Santoro Solving the robots gathering problem |
Markus Holzer, Martin Kutrib Flip-pushdown automata: k+1 pushdown reversals are better than k | |
| 15.00 - 15.15 | Closing - Blauwe zaal | |