28. ICALP 2001: Heraklion, Crete, Greece

Keynote Papers

• Christos H. Papadimitriou:
  Algorithms, Games, and the Internet. 1-3
  
• Boris A. Trakhtenbrot:
  Automata, Circuits, and Hybrids: Facets of Continuous Time. 4-23
  

Invited Papers

• Ahmed Bouajjani:
  Languages, Rewriting Systems, and Verification of Infinite-State Systems. 24-39
  
• Martin Große-Rhode:
  Integrating Semantics for Object-Oriented System Models. 40-60
  
• Mogens Nielsen:
  Modelling with Partial Orders - Why and Why Not? 61-63
  
• Ingo Wegener:
  Theoretical Aspects of Evolutionary Algorithms. 64-78
  

Algebraic and Circuit Complexity

• Markus Bläser:
  Improvements of the Alder-Strassen Bound: Algebras with Nonzero Radical. 79-91
  
• Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino:
  On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities. 92-103
  
• William Hesse:
  Division Is in Uniform TC⁰. 104-114
  

Algorithm Analysis

• Pankaj K. Agarwal, Lars Arge, Octavian Procopiuc, Jeffrey Scott Vitter:
  A Framework for Index Bulk Loading and Dynamization. 115-127
  
• Gianfranco Bilardi, Enoch Peserico:
  A Characterization of Temporal Locality and Its Portability across Memory Hierarchies. 128-139
  
• Gerth Stølting Brodal, Rolf Fagerberg, Christian N. S. Pedersen, Anna Östlin:
  The Complexity of Constructing Evolutionary Trees Using Experiments. 140-151
  
• Philippe Flajolet, Yves Guivarc'h, Wojciech Szpankowski, Brigitte Vallée:
  Hidden Pattern Statistics. 152-165
  
• Kunihiko Sadakane, Nadia Takki-Chebihi, Takeshi Tokuyama:
  Combinatorics and Algorithms on Low-Discrepancy Roundings of a Real Sequence. 166-177
  
• Alexandre Tiskin:
  All-Pairs Shortest Paths Computation in the BSP Model. 178-189
  

Approximation and Optimization

• Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan:
  Approximating the Minimum Spanning Tree Weight in Sublinear Time. 190-200
  
• Lars Engebretsen, Marek Karpinski:
  Approximation Hardness of TSP with Bounded Metrics. 201-212
  
• Uriel Feige, Michael Langberg:
  The RPR² Rounding Technique for Semidefinite Programs. 213-224
  
• Rajiv Gandhi, Samir Khuller, Aravind Srinivasan:
  Approximation Algorithms for Partial Covering Problems. 225-236
  
• Steven S. Seiden:
  On the Online Bin Packing Problem. 237-248
  
• Mikkel Thorup:
  Quick k-Median, k-Center, and Facility Location for Sparse Graphs. 249-260
  

Complexity

• Jochen Alber, Henning Fernau, Rolf Niedermeier:
  Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems. 261-272
  
• Liming Cai, David W. Juedes:
  Subexponential Parameterized Algorithms Collapse the W-Hierarchy. 273-284
  
• Amit Chakrabarti, Subhash Khot:
  Improved Lower Bounds on the Randomized Complexity of Graph Properties. 285-296
  
• Yevgeniy Dodis:
  New Imperfect Random Source with Applications to Coin-Flipping. 297-309
  
• Joel Friedman, Andreas Goerdt:
  Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently. 310-321
  
• Martin Fürer:
  Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations. 322-333
  
• Oded Goldreich, Salil P. Vadhan, Avi Wigderson:
  On Interactive Proofs with a Laconic Prover. 334-345
  
• Peter Høyer, Jan Neerbek, Yaoyun Shi:
  Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness. 346-357
  
• Pranab Sen, Srinivasan Venkatesh:
  Lower Bounds in the Quantum Cell Probe Model. 358-369
  

Concurrency

• Emanuele Bandini, Roberto Segala:
  Axiomatizations for Probabilistic Bisimulation. 370-381
  
• Gérard Boudol, Ilaria Castellani:
  Noninterference for Concurrent Programs. 382-395
  
• P. Madhusudan, P. S. Thiagarajan:
  Distributed Controller Synthesis for Local Specifications. 396-407
  
• Davide Sangiorgi, Andrea Valente:
  A Distributed Abstract Machine for Safe Ambients. 408-420
  
• Franck van Breugel, James Worrell:
  Towards Quantitative Verification of Probabilistic Transition Systems. 421-432
  

Efficient Datastructures

• Zhangjian Li, Shin-Ichi Nakano:
  Efficient Generation of Plane Triangulations without Repetitions. 433-443
  
• Guo-Hui Lin, Zhi-Zhong Chen, Tao Jiang, Jianjun Wen:
  The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations. 444-455
  
• Sang-Min Park, Jae-Ha Lee, Kyung-Yong Chwa:
  Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher. 456-468
  
• Salvador Roura:
  A New Method for Balancing Binary Search Trees. 469-480
  

Graph Algorithms

• Graham Cormode, S. Muthukrishnan, Süleyman Cenk Sahinalp:
  Permutation Editing and Matching via Embeddings. 481-492
  
• Artur Czumaj, Christian Sohler:
  Testing Hypergraph Coloring. 493-505
  
• Shuji Isobe, Xiao Zhou, Takao Nishizeki:
  Total Colorings of Degenerated Graphs. 506-517
  
• Luciano Margara, Janos Simon:
  Decidable Properties of Graphs of All-Optical Networks. 518-529
  
• Nabil H. Mustafa, Aleksandar Pekec:
  Majority Consensus and the Local Majority Rule. 530-542
  

Language Theory, Codes, and Automata

• Volker Diekert, Anca Muscholl:
  Solvability of Equations in Free Partially Commutative Groups Is Decidable. 543-554
  
• Manfred Droste, Guo-Qiang Zhang:
  Rational Transformations of Formal Power Series. 555-566
  
• Sébastien Ferenczi, Charles Holton, Luca Q. Zamboni:
  Combinatorics of Three-Interval Exchanges. 567-578
  
• Tero Harju, Oscar H. Ibarra, Juhani Karhumäki, Arto Salomaa:
  Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages. 579-590
  
• Daniel Kirsten:
  The Star Problem in Trace Monoids: Reductions Beyond C4. 591-602
  
• Michal Kunc:
  The Trace Coding Problem Is Undecidable. 603-614
  
• Eric Rivals, Sven Rahmann:
  Combinatorics of Periods in Strings. 615-626
  
• Priti Shankar, P. N. A. Kumar, Harmeet Singh, B. Sundar Rajan:
  Minimal Tail-Biting Trellises for Certain Cyclic Block Codes Are Easy to Construct. 627-638
  

Model Checking and Protocol Analysis

• Parosh Aziz Abdulla, Luc Boasson, Ahmed Bouajjani:
  Effective Lossy Queue Languages. 639-651
  
• Michael Benedikt, Patrice Godefroid, Thomas W. Reps:
  Model Checking of Unrestricted Hierarchical State Machines. 652-666
  
• Michele Boreale:
  Symbolic Trace Analysis of Cryptographic Protocols. 667-681
  
• Hubert Comon, Véronique Cortier, John Mitchell:
  Tree Automata with One Memory, Set Constraints, and Ping-Pong Protocols. 682-693
  
• Kousha Etessami, Thomas Wilke, Rebecca A. Schuller:
  Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata. 694-707
  
• Georg Gottlob, Reinhard Pichler:
  Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width. 708-719
  
• Anca Muscholl, Doron Peled:
  From Finite State Communication Protocols to High-Level Message Sequence Charts. 720-731
  

Networks and Routing

• Ioannis Caragiannis, Afonso Ferreira, Christos Kaklamanis, Stephane Perennes, Hervé Rivano:
  Fractional Path Coloring with Applications to WDM Networks. 732-743
  
• Edith Cohen, Eran Halperin, Haim Kaplan:
  Performance Aspects of Distributed Caches Using TTL-Based Consistency. 744-756
  
• Pierre Fraigniaud, Cyril Gavoille:
  Routing in Trees. 757-772
  
• Jessen T. Havill:
  Online Packet Routing on Linear Arrays and Rings. 773-784
  
• Jop F. Sibeyn:
  Faster Gossiping on Butterflies. 785-796
  

Reasoning and Verification

• Rajeev Alur, Kousha Etessami, Mihalis Yannakakis:
  Realizability and Verification of MSC Graphs. 797-808
  
• P. Madhusudan:
  Reasoning about Sequential and Branching Behaviours of Message Sequence Graphs. 809-820
  
• Patrick Maier:
  A Set-Theoretic Framework for Assume-Guarantee Reasoning. 821-834
  
• Mahesh Viswanathan, Ramesh Viswanathan:
  Foundations for Circular Compositional Reasoning. 835-847
  

Scheduling

• Chandra Chekuri, Sanjeev Khanna:
  A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines. 848-861
  
• Marek Chrobak, János Csirik, Csanád Imreh, John Noga, Jiri Sgall, Gerhard J. Woeginger:
  The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts. 862-874
  
• Aleksei V. Fishkin, Klaus Jansen, Lorant Porkolab:
  On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates. 875-886
  
• Gerhard J. Woeginger:
  On the Approximability of Average Completion Time Scheduling under Precedence Constraints. 887-897
  

Secure Computation

• Birgit Baum-Waidner:
  Optimistic Asynchronous Multi-party Contract Signing with Reduced Number of Rounds. 898-911
  
• Amos Beimel, Yuval Ishai:
  Information-Theoretic Private Information Retrieval: A Unified Construction. 912-926
  
• Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin Strauss, Rebecca N. Wright:
  Secure Multiparty Computation of Approximations. 927-938
  
• Aggelos Kiayias, Moti Yung:
  Secure Games with Polynomial Expressions. 939-950
  

Specification and Deduction

• Miquel Bofill, Guillem Godoy:
  On the Completeness of Arbitrary Selection Strategies for Paramodulation. 951-962
  
• Furio Honsell, Marino Miculan, Ivan Scagnetto:
  An Axiomatic Approach to Metareasoning on Nominal Algebras in HOAS. 963-978
  
• Konstantin Korovin, Andrei Voronkov:
  Knuth-Bendix Constraint Solving Is NP-Complete. 979-992
  
• Lutz Schröder, Till Mossakowski, Andrzej Tarlecki:
  Amalgamation in CASL via Enriched Signatures. 993-1004
  

Structural Complexity

• Albert Atserias, Maria Luisa Bonet, Juan Luis Esteban:
  Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution. 1005-1016
  
• Harry Buhrman, John Tromp, Paul M. B. Vitányi:
  Time and Space Bounds for Reversible Simulation. 1017-1027
  
• Jack Jie Dai, James I. Lathrop, Jack H. Lutz, Elvira Mayordomo:
  Finite-State Dimension. 1028-1039
  
• Lane A. Hemaspaandra, Sven Kosub, Klaus W. Wagner:
  The Complexity of Computing the Size of an Interval. 1040-1051
  
• Tomasz Jurdzinski, Miroslaw Kutylowski:
  Communication Gap for Finite Memory Devices. 1052-1064
  
• Rocco A. Servedio:
  Separating Quantum and Classical Learning. 1065-1080