list accepted papers for ICALP 2003

[icalp2003 at TUE.nl]

-------------------------------------------------------------------------

     We apologize for the reception of multiple copies of this message.
----------------------------------------------------------------------------
----------------------------


============================================================================
==========

  List of papers accepted for ICALP'2003, Track A and Track B 

  Eindhoven, The Netherlands, June 30 - July 4, 2003
  http://www.win.tue.nl/icalp2003/

============================================================================
==========


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 dynamic tree networks

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

============================================================================
==========







-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.