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 klevel 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 cacheoblivious 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 boundederror 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 SPQRtree 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 (2k1)Spanner of O(n^{1+1/k}) size in weighted graphs 
Juraj Hromkovic, Georg
Schnitger Nondeterminisn versus determinism for twoway 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 EvenDar, 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 1counter 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 2server problem 
Felix Klaedtke, Harald Ruess Monadic secondorder 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 contextdependent properties  
Randeep Bhatia, Julia Chuzhoy,
Ari Freund, Joseph Naor Algorithmic aspects of bandwidth trading 
Philippe Schnoebelen
Oracle circuits for branchingtime 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
lambdacalculus 
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 Fixedparameter 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 higherorder 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 degreerestricted MST and redblue separation problem 
ErnstErich Doberkat Semipullbacks and bisimulations in categories of stochastic relations  
Chandra Chekuri, Sudipto Guha, Joseph Naor Approximating Steiner kcuts 
Alexander Rabinovich Quantitative analysis of probabilistic lossy channel systems  
Amin CojaOghlan, Cristopher Moore, Vishal Sanwalani MAX kCUT 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 Online 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 Realtime scheduling with a budget  
Dominique Poulalhon, Gilles Schaeffer Optimal coding and sampling of triangulations 
Brian Dean, Michel Goemans Improved approximation algorithms for minimumspace 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 tturn DPDA is coNP  
Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, Nicola
Santoro Solving the robots gathering problem 
Markus Holzer, Martin Kutrib Flippushdown automata: k+1 pushdown reversals are better than k  
15.00  15.15  Closing  Blauwe zaal 