Program ICALP2003

Invited speakers
Schedule
List of accepted papers

Invited speakers

Schedule

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




List of papers accepted for ICALP2003, Track A and Track B



Vincent Blondel, Paul Van Dooren
Similarity matrices for pairs of graphs

Arnold Schoenhage
Adaptive raising strategies optimizing relative efficiency

Sergei Bespamyatnikh, Michael Segal
Dynamic algorithms for approximating interdistances

Amos Korman, David Peleg
Labeling Schemes for Weighted Dynamic Trees

Geraud Senizergues
The equivalence problem for t-turn DPDA is co-NP

John Hitchcock, Jack Lutz, Elvira Mayordomo
Scaled dimension and nonuniform complexity

Yossi Matias, Ely Porat
Efficient pebbling for list traversal synopses

Alexander Ageev, Yinyu Ye, Jiawei Zhang
Improved combinatorial approximation algorithms for the k-level facility location problem

Markus Blaeser
An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality

Susanne Albers, Rob van Stee
A study of integrated document and connection caching

Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein, Ely Porat
Function matching: algorithms, applications, and a lower bound

Eyal Even-Dar, Alex Kesselman, Yishay Mansour
Convergence time to Nash equilibria

Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani
MAX k-CUT and approximating the chromatic number of random graphs

Jiri Fiala, Daniel Paulusma
The computational complexity of the role assignment problem

Vipul Bansal, Aseem Agrawal, Varun Malhotra
Stable marriages with multiple partners: efficient search for an optimal solution

Juraj Hromkovic, Georg Schnitger
Pushdown automata and multicounter machines, a comparison of computation mode

Jens Jaegerskuepper
Analysis of a simple evolutionary algorithm for minimization in Euclidean spaces

Noam Berger, Bela Bollobas, Christian Borgs, Jennifer Chayes, Oliver Riordan
Degree distribution of the FKP network model

Luisa Gargano, Mikael Hammar
There are spanning spiders in dense graphs (and we know how to find them)

Annalisa De Bonis, Leszek Gasieniec, Ugo Vaccaro
Generalized framework for selectors with applications in optimal group testing

Michael Elkin, Guy Kortsarz
Approximation algorithm for the directed telephone multicast problem

Sanjeev Arora, Kevin Chang
Approximation schemes for degree-restricted MST and red-blue separation problem

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

Chandra Chekuri, Marcelo Mydlarz, Bruce Shepherd
Multicommodity demand flow in a tree

Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph Naor
Algorithmic aspects of bandwidth trading

Chandra Chekuri, Sudipto Guha, Joseph Naor
Approximating Steiner k-cuts

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino
An intersection inequality for discrete distributions and related generation problems

Erik Demaine, Fedor Fomin, MohammadTaghi Hajiaghayi, Dimitrios Thilikos
Fixed-parameter algorithms for the (k,r)-center in planar graphs and map graphs

Gianni Franceschini, Roberto Grossi
Optimal cache-oblivious implicit dictionaries

Anna Gal, Peter Bro Miltersen
The cell probe complexity of succinct data structures

Alex Hall, Steffen Hippler, Martin Skutella
Multicommodity flows over time: efficient algorithms and complexity

Rene Sitters, Leen Stougie, Willem Paepe
A competitive algorithm for the general 2-server problem

Luis Antunes, Lance Fortnow
Sophistication revisited

Peter Hoyer, Michele Mosca, Ronald de Wolf
Quantum search on bounded-error inputs

Dimitris Fotakis
On the competitive ratio for online facility location

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

Seffi Naor, Hadas Shachnai, Tami Tamir
Real-time scheduling with a budget

Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro
Solving the robots gathering problem

Rainer Feldmann, Martin Gairing, Thomas Luecking, Burkhard Monien, Manuel Rode
Nashification and the coordination ratio for a selfish routing game

Brian Dean, Michel Goemans
Improved approximation algorithms for minimum-space advertisement scheduling

Baruch Awerbuch, Andre Brinkmann, Christian Scheideler
Anycasting in adversarial systems: routing and admission control

Jianer Chen, Iyad Kanj, Ljubomir Perkovic, Eric Sedgwick, Ge Xia
Genus characterizes the complexity of graph problems: some tight results

Markus Holzer, Martin Kutrib
Flip-pushdown automata: k+1 pushdown reversals are better than k

Manuel Bodirsky, Clemens Gröpl, Mihyun Kang
Generating labeled planar graphs uniformly at random

Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan
An improved approximation algorithm for vertex cover with hard capacities

Dominique Poulalhon, Gilles Schaeffer
Optimal coding and sampling of triangulations

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

Daniel Bleichenbacher, Aggelos Kiayias, Moti Yung
Decoding of interleaved Reed Solomon codes over noisy data

Juha Kärkkäinen, Peter Sanders
Simple linear work suffix array construction

Manfred Droste, Dietrich Kuske
Skew and infinitary formal power series

Ernst-Erich Doberkat
Semi-pullbacks and bisimulations in categories of stochastic relations

Stefan Blom, Wan Fokkink, Sumit Nain
On the axiomatizability of ready traces, ready simulation and failure traces

Juraj Hromkovic, Georg Schnitger
Nondeterminisn versus determinism for two-way finite automata: generalizations of Sipser's separation

Daniele Gorla, Rosario Pugliese
Resource access and mobility control with dynamic privileges acquisition

Jan Johannsen, Martin Lange
CTL+ is complete for double exponential time

Davide Ancona, Sonia Fagorzi, Eugenio Moggi, Elena Zucca
Mixin modules and computational effects

Thierry Cachat
Higher order pushdown automata, the Caucal hierarchy of graphs and parity games

Gaoyan Xie, Zhe Dang, Oscar Ibarra
A solvable class of quadratic Diophantine equations with applications to verification of infinite state systems

Alexander Okhotin
Decision problems for language equations with Boolean operations

Roberto Bruni, Jose Meseguer
Generalized rewrite theories

Salvatore La Torre, Margherita Napoli, Mimmo Parente, Gennaro Parlato
Hierarchical and recursive state machines with context-dependent properties

Cindy Eisner, Dana Fisman, John Havlicek, Anthony McIsaac, David Van Campenhout
The definition of a temporal clock operator

Nadia Busi, Maurizio Gabbrielli, Gianluigi Zavattaro
Replication vs. recursive definitions in channel based calculi

Richard Mayr
Undecidability of weak bisimulation equivalence for 1-counter processes

Felix Klaedtke, Harald Ruess
Monadic second-order logics with cardinalities

Orna Kupferman, Moshe Vardi
Pi_2 intersected Sigma_2 equals AFMC

Alexander Rabinovich
Quantitative analysis of probabilistic lossy channel systems

Massimo Merro, Francesco Zappa Nardelli
Bisimulation proof methods for mobile ambients

Tatiana Rybina, Andrei Voronkov
Upper bounds for a theory of queues

Zena Ariola, Hugo Herbelin
Minimal classical logic and control operators

Arnaud Carayol, Thomas Colcombet
On equivalent representations of infinite structures

Philippe Schnoebelen
Oracle circuits for branching-time model checking

Luca de Alfaro, Thomas A. Henzinger, Rupak Majumdar
Discounting the future in systems theory

Thomas Henzinger, Ranjit Jhala, Rupak Majumdar
Counterexample guided control

Jo Hannay
Axiomatic criteria for quotients and subobjects for higher-order data types

Francois Denis, Yann Esposito
Residual languages and probabilistic automata

Francisco Gutierrez, Blas Ruiz
Expansion postponement via cut elimination in sequent calculi for pure type systems

Michele Bugliesi, Silvia Crafa, Amela Prelic, Vladimiro Sassone
Secrecy in untrusted networks

Luca de Alfaro, Marco Faella
Information flow in concurrent games

Marielle Stoelinga , Frits Vaandrager
A testing scenario for probabilistic automata

Arkadev Chattopadhyay, Denis Therien
Locally commutative categories