27. ICALP 2000: Geneva, Switzerland

• Samson Abramsky:
  Game Semantics: Achievements and Prospects. 1
  
• Lars Engebretsen, Jonas Holmerin:
  Clique Is Hard to Approximate within n^1-o(1). 2-12
  
• Michael Krivelevich, Van H. Vu:
  Approximating the Independence Number and the Chromatic Number in Expected Polynominal Time. 13-24
  
• Cristiano Calcagno, Eugenio Moggi, Walid Taha:
  Closed Types as a Simple Approach to Safe Imperative Multi-stage Programming. 25-36
  
• Alan Mycroft, Richard Sharp:
  A Statically Allocated Parallel Functional Language. 37-48
  
• Seth Pettie, Vijaya Ramachandran:
  An Optimal Minimum Spanning Tree Algorithm. 49-60
  
• Torben Hagerup:
  Improved Shortest Paths on the Word RAM. 61-72
  
• Stephen Alstrup, Jacob Holm:
  Improved Algorithms for Finding Level Ancestors in Dynamic Trees. 73-84
  
• Gordon D. Plotkin, John Power, Donald Sannella, Robert D. Tennent:
  Lax Logical Relations. 85-102
  
• Dan R. Ghica, Guy McCusker:
  Reasoning about Idealized ALGOL Using Regular Languages. 103-115
  
• Keye Martin:
  The Measurement Process in Domain Theory. 116-126
  
• Gregor Engels, Reiko Heckel:
  Graph Transformation as a Conceptual and Formal Framework for System Modeling and Model Evolution. 127-150
  
• Albert Atserias, Nicola Galesi, Ricard Gavaldà:
  Monotone Proofs of the Pigeon Hole Principle. 151-162
  
• Gerald Lüttgen, Michael Mendler:
  Fully-Abstract Statecharts Semantics via Intuitionistic Kripke Models. 163-174
  
• Roberto Bruni, Vladimiro Sassone:
  Algebraic Models for Contextual Nets. 175-186
  
• Beate Bollig, Ingo Wegener:
  Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems. 187-198
  
• Juraj Hromkovic, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert:
  Measures of Nondeterminism in Finite Automata. 199-210
  
• Volker Diekert, Paul Gastin:
  LTL Is Expressively Complete for Mazurkiewicz Traces. 211-222
  
• Ben C. Moszkowski:
  An Automata-Theoretic Completeness Proof for Interval Temporal Logic. 223-234
  
• Johan Håstad:
  Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? 235
  
• Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning:
  Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search. 236-247
  
• Johannes Blömer:
  Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices. 248-259
  
• Leonid Libkin:
  Variable Independence, Quantifier Elimination, and Constraint Representations. 260-271
  
• Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons:
  Constraint Satisfaction Problems and Finite Algebras. 272-282
  
• Steven S. Seiden:
  An Optimal Online Algorithm for Bounded Space Variable-Sized Bin Packing. 283-295
  
• János Csirik, Gerhard J. Woeginger:
  Resource Augmentation for Online Bounded Space Bin Packing. 296-304
  
• Christoph Ambühl, Bernd Gärtner, Bernhard von Stengel:
  Optimal Projective Algorithms for the List Update Problem. 305-316
  
• Antonín Kucera:
  Efficient Verification Algorithms for One-Counter Processes. 317-328
  
• Richard Mayr:
  On the Complexity of Bisimulation Problems for Basic Parallel Processes. 329-341
  
• Denis Lugiez, Ph. Schnoebelen:
  Decidable First-Order Transition Logics for PA-Processes. 342-353
  
• Riccardo Focardi, Roberto Gorrieri, Fabio Martinelli:
  Non Interference for the Analysis of Cryptographic Protocols. 354-372
  
• Ali Akhavi, Brigitte Vallée:
  Average Bit-Complexity of Euclidean Algorithms. 373-387
  
• Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michèle Soria:
  Planar Maps and Airy Phenomena. 388-402
  
• Barbara König:
  Analysing Input/Output-Capabilities of Mobile Processes with a Generic Type System. 403-414
  
• Matthew Hennessy, James Riely:
  Information Flow vs. Resource Access in the Asynchronous Pi-Calculus. 415-427
  
• Richard M. Karp:
  The Genomics Revolution and Its Challenges for Algorithmic Research. 428
  
• Zohar Manna, Henny Sipma:
  Alternating the Temporal Picture for Safety. 429-450
  
• Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano:
  Necessary and Sufficient Assumptions for Non-iterative Zero-Knowledge Proofs of Knowledge for All NP Relations. 451-462
  
• William Aiello, Sandeep N. Bhatt, Rafail Ostrovsky, Sivaramakrishnan Rajagopalan:
  Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP. 463-474
  
• Javier Esparza, Keijo Heljanko:
  A New Unfolding Approach to LTL Model Checking. 475-486
  
• B. Meenakshi, Ramaswamy Ramanujam:
  Reasoning about Message Passing in Finite State Environments. 487-498
  
• Olivier Baudron, David Pointcheval, Jacques Stern:
  Extended Notions of Security for Multicast Public Key Cryptosystems. 499-511
  
• Christian Cachin, Jan Camenisch, Joe Kilian, Joy Müller:
  One-Round Secure Computation and Secure Autonomous Mobile Agents. 512-523
  
• Birgit Baum-Waidner, Michael Waidner:
  Round-Optimal and Abuse Free Optimistic Multi-party Contract Signing. 524-535
  
• Juhani Karhumäki, Ion Petre:
  On the Centralizer of a Finite Set. 536-546
  
• Frank Neven, Thomas Schwentick:
  On the Power of Tree-Walking Automata. 547-560
  
• Marie-Pierre Béal, Olivier Carton:
  Determinization of Transducers over Infinite Words. 561-570
  
• Kurt Mehlhorn:
  Constraint Programming and Graph Algorithms. 571-575
  
• Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien P. Stern:
  Scalable Secure Storage when Half the System Is Faulty. 576-587
  
• Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino:
  Generating Partial and Multiple Transversals of a Hypergraph. 588-599
  
• José Espírito Santo:
  Revisiting the Correspondence between Cut Elimination and Normalisation. 600-611
  
• Reinhard Pichler:
  Negation Elimination from Simple Equational Formulae. 612-623
  
• V. S. Anil Kumar, Sunil Arya, H. Ramesh:
  Hardness of Set Cover with Intersection 1. 624-635
  
• Michael Elkin, David Peleg:
  Strong Inapproximability of the Basic k-Spanner Problem. 636-647
  
• Dietrich Kuske:
  Infinite Series-Parallel Posets: Logic and Languages. 648-662
  
• Tomasz Fryderyk Urbanski:
  On Deciding if Deterministic Rabin Language Is in Büchi Class. 663-674
  
• Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P. S. Thiagarajan:
  On Message Sequence Graphs and Finitely Generated Regular MSC Languages. 675-686
  
• Oded Goldreich:
  Pseudorandomness. 687-704
  
• Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson:
  A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. 705-716
  
• Bogdan S. Chlebus, Leszek Gasieniec, Anna Östlin, John Michael Robson:
  Deterministic Radio Broadcasting. 717-728
  
• Wan Fokkink, S. P. Luttik:
  An omega-Complete Equational Specification of Interleaving. 729-743
  
• Mario Bravetti, Roberto Gorrieri:
  A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors. 744-755
  
• Micah Adler, Faith E. Fich, Leslie Ann Goldberg, Mike Paterson:
  Tight Size Bounds for Packet Headers in Narrow Meshes. 756-767
  
• Luciano Margara, Janos Simon:
  Wavelength Assignment Problem on All-Optical Networks with k Fibres per Link. 768-779
  
• Christel Baier, Boudewijn R. Haverkort, Holger Hermanns, Joost-Pieter Katoen:
  On the Logical Characterisation of Performability Properties. 780-792
  
• Olivier Bournez, Oded Maler:
  On the Representation of Timed Polyhedra. 793-807
  
• Andrei Z. Broder:
  Min-wise Independent Permutations: Theory and Practice. 808
  
• Michael A. Bender, Dana Ron:
  Testing Acyclicity of Directed Graphs in Sublinear Time. 809-820
  
• Hristo Djidjev:
  Computing the Girth of a Planar Graph. 821-831
  
• Hervé Fournier, Pascal Koiran:
  Lower Bounds Are Not Easier over the Reals: Inside PH. 832-843
  
• Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan:
  Unlearning Helps. 844-855
  
• Artur Czumaj, Andrzej Lingas:
  Fast Approximation Schemes for Euclidean Multi-connectivity Problems. 856-868
  
• Michelangelo Grigni:
  Approximate TSP in Graphs with Forbidden Minors. 869-877
  
• Klaus Jansen, Lorant Porkolab:
  Polynominal Time Approximation Schemes for General Multiprocessor Job Shop Scheduling. 878-889
  
• Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer:
  The Many Faces of a Translation. 890-901
  
• Jack H. Lutz:
  Gales and the Constructive Dimension of Individual Sequences. 902-913
  
• Wolfgang Merkle:
  The Global Power of Additional Queries to p-Random Oracles. 914-925
  
• Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi:
  Homogenization and the Polynominal Calculus. 926-937