=09charset=3D"iso-8859-1" Sender: cat-dist@mta.ca Precedence: bulk ------------------------------------------------------------------------- We apologize for the reception of multiple copies of this message. ---------------------------------------------------------------------------= - ---------------------------- =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D 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/ =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D 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 strengthene= d 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 Riorda= n 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, Kazuhis= a Makino An intersection inequality for discrete distributions and related generatio= n 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 schedulin= g 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=F6pl, Mihyun Kang Generating labeled planar graphs uniformly at random Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasa= n 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=E4rkk=E4inen, 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 trace= s 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 =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D