内容

目次

Invited Talk.- Game Semantics: Achievements and Prospects.- Clique Is Hard to Approximate within n 1-o(1).- Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time.- Closed Types as a Simple Approach to Safe Imperative Multi-stage Programming.- A Statically Allocated Parallel Functional Language.- An Optimal Minimum Spanning Tree Algorithm.- Improved Shortest Paths on the Word RAM.- Improved Algorithms for Finding Level Ancestors in Dynamic Trees.- Lax Logical Relations.- Reasoning about Idealized ALGOL Using Regular Languages.- The Measurement Process in Domain Theory.- Invited Talk.- Graph Transformation as a Conceptual and Formal Framework for System Modeling and Model Evolution.- Monotone Proofs of the Pigeon Hole Principle.- Fully-Abstract Statecharts Semantics via Intuitionistic Kripke Models.- Algebraic Models for Contextual Nets.- Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems.- Measures of Nondeterminism in Finite Automata.- LTL Is Expressively Complete for Mazurkiewicz Traces.- An Automata-Theoretic Completeness Proof for Interval Temporal Logic.- Invited Talk.- Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?.- Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search.- Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices.- Variable Independence, Quantifier Elimination, and Constraint Representations.- Constraint Satisfaction Problems and Finite Algebras.- An Optimal Online Algorithm for Bounded Space Variable-Sized Bin Packing.- Resource Augmentation for Online Bounded Space Bin Packing.- Optimal Projective Algorithms for the List Update Problem.- Efficient Verification Algorithms for One-Counter Processes.- On the Complexity of Bisimulation Problems for Basic Parallel Processes.- Decidable First-Order Transition Logics for PA-Processes.- Invited Talk.- Non Interference for the Analysis of Cryptographic Protocols.- Average Bit-Complexity of Euclidean Algorithms.- Planar Maps and Airy Phenomena.- Analysing Input/Output-Capabilities of Mobile Processes with a Generic Type System.- Information Flow vs. Resource Access in the Asynchronous Pi-Calculus (Extended Abstract).- Award Talk.- The Genomics Revolution and Its Challenges for Algorithmic Research.- Invited Talk.- Alternating the Temporal Picture for Safety.- Necessary and Sufficient Assumptions for Non-interactive Zero-Knowledge Proofs of Knowledge for All NP Relations.- Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP.- A New Unfolding Approach to LTL Model Checking.- Reasoning about Message Passing in Finite State Environments.- Extended Notions of Security for Multicast Public Key Cryptosystems.- One-Round Secure Computation and Secure Autonomous Mobile Agents.- Round-Optimal and Abuse-Free Optimistic Multi-party Contract Signing.- On the Centralizer of a Finite Set.- On the Power of Tree-Walking Automata.- Determinization of Transducers over Infinite Words.- Invited Talk.- Constraint Programming and Graph Algorithms.- Scalable Secure Storage when Half the System Is Faulty.- Generating Partial and Multiple Transversals of a Hypergraph.- Revisiting the Correspondence between Cut Elimination and Normalisation.- Negation Elimination from Simple Equational Formulae.- Hardness of Set Cover with Intersection 1.- Strong Inapproximability of the Basic k-Spanner Problem.- Infinite Series-Parallel Posets: Logic and Languages.- On Deciding if Deterministic Rabin Language Is in Büchi Class.- On Message Sequence Graphs and Finitely Generated Regular MSC Languages.- Invited Talk.- Pseudorandomness.- A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols.- Deterministic Radio Broadcasting.- An ?-Complete Equational Specification of Interleaving.- A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors.- Tight Size Bounds for Packet Headers in Narrow Meshes.- Wavelength Assignment Problem on All-Optical Networks with k Fibres per Link.- On the Logical Characterisation of Performability Properties.- On the Representation of Timed Polyhedra.- Invited Talk.- Min-wise Independent Permutations: Theory and Practice.- Testing Acyclicity of Directed Graphs in Sublinear Time.- Computing the Girth of a Planar Graph.- Lower Bounds Are Not Easier over the Reals: Inside PH.- Unlearning Helps.- Fast Approximation Schemes for Euclidean Multi-connectivity Problems.- Approximate TSP in Graphs with Forbidden Minors.- Polynomial Time Approximation Schemes for General Multiprocessor Job Shop Scheduling.- The Many Faces of a Translation.- Gales and the Constructive Dimension of Individual Sequences.- The Global Power of Additional Queries to p-Random Oracles.- Homogenization and the Polynomial Calculus.