30. ICALP 2003: Eindhoven, The Netherlands

Invited Lectures

• Jan A. Bergstra, Inge Bethke:
  Polarized Process Algebra and Program Equivalence. 1-21
  
• Anne Condon:
  Problems on RNA Secondary Structure Prediction and Design. 22-32
  
• Amos Fiat:
  Some Issues Regarding Search, Censorship, and Anonymity in Peer to Peer Networks. 33
  
• Petra Mutzel:
  The SPQR-Tree Data Structure in Graph Drawing. 34-46
  
• Doron Peled:
  Model Checking and Testing Combined. 47-63
  
• Moshe Y. Vardi:
  Logic and Automata: A Match Made in Heaven. 64-65
  

Algorithms

• Juraj Hromkovic, Georg Schnitger:
  Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes. 66-80
  
• Annalisa De Bonis, Leszek Gasieniec, Ugo Vaccaro:
  Generalized Framework for Selectors with Applications in Optimal Group Testing. 81-96
  
• Daniel Bleichenbacher, Aggelos Kiayias, Moti Yung:
  Decoding of Interleaved Reed Solomon Codes over Noisy Data. 97-108
  

Process Algebra

• Stefan Blom, Wan Fokkink, Sumit Nain:
  On the Axiomatizability of Ready Traces, Ready Simulation, and Failure Traces. 109-118
  
• Daniele Gorla, Rosario Pugliese:
  Resource Access and Mobility Control with Dynamic Privileges Acquisition. 119-132
  
• Nadia Busi, Maurizio Gabbrielli, Gianluigi Zavattaro:
  Replication vs. Recursive Definitions in Channel Based Calculi. 133-144
  

Approximation Algorithms

• Alexander A. Ageev, Yinyu Ye, Jiawei Zhang:
  Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem. 145-156
  
• Markus Bläser:
  An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality. 157-163
  
• Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan:
  An Improved Approximation Algorithm for Vertex Cover with Hard Capacities. 164-175
  
• Sanjeev Arora, Kevin L. Chang:
  Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem. 176-188
  
• Chandra Chekuri, Sudipto Guha, Joseph Naor:
  Approximating Steiner k-Cuts. 189-199
  
• Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani:
  MAX k-CUT and Approximating the Chromatic Number of Random Graphs. 200-211
  
• Michael Elkin, Guy Kortsarz:
  Approximation Algorithm for Directed Telephone Multicast Problem. 212-223
  

Languages and Programming

• Davide Ancona, Sonia Fagorzi, Eugenio Moggi, Elena Zucca:
  Mixin Modules and Computational Effects. 224-238
  
• Alexander Okhotin:
  Decision Problems for Language Equations with Boolean Operations. 239-251
  
• Roberto Bruni, José Meseguer:
  Generalized Rewrite Theories. 252-266
  

Complexity

• Luis Antunes, Lance Fortnow:
  Sophistication Revisited. 267-277
  
• John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo:
  Scaled Dimension and Nonuniform Complexity. 278-290
  
• Peter Høyer, Michele Mosca, Ronald de Wolf:
  Quantum Search on Bounded-Error Inputs. 291-299
  
• Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen:
  A Direct Sum Theorem in Communication Complexity via Message Compression. 300-315
  

Data Structures

• Gianni Franceschini, Roberto Grossi:
  Optimal Cache-Oblivious Implicit Dictionaries. 316-331
  
• Anna Gál, Peter Bro Miltersen:
  The Cell Probe Complexity of Succinct Data Structures. 332-344
  
• J. Ian Munro, Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao:
  Succinct Representations of Permutations. 345-356
  
• Rajeev Raman, S. Srinivasa Rao:
  Succinct Dynamic Dictionaries and Trees. 357-368
  

Graph Algorithms

• Amos Korman, David Peleg:
  Labeling Schemes for Weighted Dynamic Trees. 369-383
  
• 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. 384-296
  
• Alexander Hall, Steffen Hippler, Martin Skutella:
  Multicommodity Flows over Time: Efficient Algorithms and Complexity. 397-409
  
• Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd:
  Multicommodity Demand Flow in a Tree. 410-425
  

Automata

• Manfred Droste, Dietrich Kuske:
  Skew and Infinitary Formal Power Series. 426-438
  
• Juraj Hromkovic, Georg Schnitger:
  Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser's Separation. 439-451
  
• François Denis, Yann Esposito:
  Residual Languages and Probabilistic Automata. 452-463
  
• Mariëlle Stoelinga, Frits W. Vaandrager:
  A Testing Scenario for Probabilistic Automata. 464-477
  
• Géraud Sénizergues:
  The Equivalence Problem for t-Turn DPDA Is Co-NP. 478-489
  
• Markus Holzer, Martin Kutrib:
  Flip-Pushdown Automata: k+1 Pushdown Reversals Are Better than k. 490-501
  

Optimization and Games

• Eyal Even-Dar, Alexander Kesselman, Yishay Mansour:
  Convergence Time to Nash Equilibria. 502-513
  
• Rainer Feldmann, Martin Gairing, Thomas Lücking, Burkhard Monien, Manuel Rode:
  Nashification and the Coordination Ratio for a Selfish Routing Game. 514-526
  
• Vipul Bansal, Aseem Agrawal, Varun S. Malhotra:
  Stable Marriages with Multiple Partners: Efficient Search for an Optimal Solution. 527-542
  
• Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino:
  An Intersection Inequality for Discrete Distributions and Related Generation Problems. 543-555
  

Graphs and Bisimulation

• Thierry Cachat:
  Higher Order Pushdown Automata, the Caucal Hierarchy of Graphs and Parity Games. 556-569
  
• Richard Mayr:
  Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes. 570-583
  
• Massimo Merro, Francesco Zappa Nardelli:
  Bisimulation Proof Methods for Mobile Ambients. 584-598
  
• Arnaud Carayol, Thomas Colcombet:
  On Equivalent Representations of Infinite Structures. 599-610
  

Online Problems

• Arnold Schönhage:
  Adaptive Raising Strategies Optimizing Relative Efficiency. 611-623
  
• René Sitters, Leen Stougie, Willem de Paepe:
  A Competitive Algorithm for the General 2-Server Problem. 624-636
  
• Dimitris Fotakis:
  On the Competitive Ratio for Online Facility Location. 637-652
  
• Susanne Albers, Rob van Stee:
  A Study of Integrated Document and Connection Caching. 653-667
  

Verification

• Gaoyan Xie, Zhe Dang, Oscar H. Ibarra:
  A Solvable Class of Quadratic Diophantine Equations with Applications to Verification of Infinite-State Systems. 668-680
  
• Felix Klaedtke, Harald Rueß:
  Monadic Second-Order Logics with Cardinalities. 681-696
  
• Orna Kupferman, Moshe Y. Vardi:
  Pi₂ cap Sigma₂ equiv AFMC. 697-713
  
• Tatiana Rybina, Andrei Voronkov:
  Upper Bounds for a Theory of Queues. 714-724
  

Around the Internet

• Noam Berger, Béla Bollobás, Christian Borgs, Jennifer T. Chayes, Oliver Riordan:
  Degree Distribution of the FKP Network Model. 725-738
  
• Vincent D. Blondel, Paul Van Dooren:
  Similarity Matrices for Pairs of Graphs. 739-750
  
• Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph Naor:
  Algorithmic Aspects of Bandwidth Trading. 751-766
  

Temporal Logic and Model Checking

• Jan Johannsen, Martin Lange:
  CTL⁺ Is Complete for Double Exponential Time. 767-775
  
• Salvatore La Torre, Margherita Napoli, Mimmo Parente, Gennaro Parlato:
  Hierarchical and Recursive State Machines with Context-Dependent Properties. 776-789
  
• Ph. Schnoebelen:
  Oracle Circuits for Branching-Time Model Checking. 790-801
  

Graph Problems

• Luisa Gargano, Mikael Hammar:
  There Are Spanning Spiders in Dense Graphs (and We Know How to Find Them). 802-816
  
• Jirí Fiala, Daniël Paulusma:
  The Computational Complexity of the Role Assignment Problem. 817-828
  
• Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
  Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs. 829-844
  
• Jianer Chen, Iyad A. Kanj, Ljubomir Perkovic, Eric Sedgwick, Ge Xia:
  Genus Characterizes the Complexity of Graph Problems: Some Tight Results. 845-856
  

Logic and Lambda-Calculus

• Cindy Eisner, Dana Fisman, John Havlicek, Anthony McIsaac, David Van Campenhout:
  The Definition of a Temporal Clock Operator. 857-870
  
• Zena M. Ariola, Hugo Herbelin:
  Minimal Classical Logic and Control Operators. 871-885
  
• Thomas A. Henzinger, Ranjit Jhala, Rupak Majumdar:
  Counterexample-Guided Control. 886-902
  
• Jo Erskine Hannay:
  Axiomatic Criteria for Quotients and Subobjects for Higher-Order Data Types. 903-917
  

Data Structures and Algorithms

• Yossi Matias, Ely Porat:
  Efficient Pebbling for List Traversal Synopses. 918-928
  
• Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein, Ely Porat:
  Function Matching: Algorithms, Applications, and a Lower Bound. 929-942
  
• Juha Kärkkäinen, Peter Sanders:
  Simple Linear Work Suffix Array Construction. 943-955
  

Types and Categories

• Francisco Gutiérrez, Blas C. Ruiz:
  Expansion Postponement via Cut Elimination in Sequent Calculi for Pure Type Systems. 956-968
  
• Michele Bugliesi, Silvia Crafa, Amela Prelic, Vladimiro Sassone:
  Secrecy in Untrusted Networks. 969-983
  
• Arkadev Chattopadhyay, Denis Thérien:
  Locally Commutative Categories. 984-995
  

Probabilistic Systems

• Ernst-Erich Doberkat:
  Semi-pullbacks and Bisimulations in Categories of Stochastic Relations. 996-1007
  
• Alexander Moshe Rabinovich:
  Quantitative Analysis of Probabilistic Lossy Channel Systems. 1008-1021
  
• Luca de Alfaro, Thomas A. Henzinger, Rupak Majumdar:
  Discounting the Future in Systems Theory. 1022-1037
  
• Luca de Alfaro, Marco Faella:
  Information Flow in Concurrent Games. 1038-1053
  

Sampling and Randomness

• Satoshi Ikeda, Izumi Kubo, Norihiro Okumoto, Masafumi Yamashita:
  Impact of Local Topological Information on Random Walks on Finite Graphs. 1054-1067
  
• Jens Jägersküpper:
  Analysis of a Simple Evolutionary Algorithm for Minimization in Euclidean Spaces. 1068-1079
  
• Dominique Poulalhon, Gilles Schaeffer:
  Optimal Coding and Sampling of Triangulations. 1080-1094
  
• Manuel Bodirsky, Clemens Gröpl, Mihyun Kang:
  Generating Labeled Planar Graphs Uniformly at Random. 1095-1107
  

Scheduling

• Pierluigi Crescenzi, Giorgio Gambosi, Gaia Nicosia, Paolo Penna, Walter Unger:
  Online Load Balancing Made Simple: Greedy Strikes Back. 1108-1122
  
• Joseph Naor, Hadas Shachnai, Tami Tamir:
  Real-Time Scheduling with a Budget. 1123-1137
  
• Brian C. Dean, Michel X. Goemans:
  Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling. 1138-1152
  
• Baruch Awerbuch, André Brinkmann, Christian Scheideler:
  Anycasting in Adversarial Systems: Routing and Admission Control. 1153-1168
  

Geometric Problems

• Sergei Bespamyatnikh, Michael Segal:
  Dynamic Algorithms for Approximating Interdistances. 1169-1180
  
• Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro:
  Solving the Robots Gathering Problem. 1181-1196
  

Last update Sat May 25 18:03:41 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page