Automata, Languages and Programming 32nd International Colloquim, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings

The 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005) was held in Lisbon, Portugal from July 11 to July 15, 2005. These proceedings contain all contributed papers presented at ICALP 2005, - getherwiththepapersbytheinvitedspeakersGiuseppeCastagna(ENS),Leonid Libkin (Toronto), John C. Mitchell (Stanford), Burkhard Monien (Paderborn), and Leslie Valiant (Harvard). The program had an additional invited lecture by Adi Shamir (Weizmann Institute) which does not appear in these proceedings. ICALP is a series of annual conferences of the European Association for Theoretical Computer Science (EATCS). The ?rst ICALP took place in 1972. This year, the ICALP program consisted of the established track A (focusing on algorithms, automata, complexity and games) and track B (focusing on logic, semantics and theory of programming), and innovated on the structure of its traditional scienti?c program with the inauguration of a new track C (focusing on security and cryptography foundation). In response to a call for papers, the Program Committee received 407 s- missions, 258 for track A, 75 for track B and 74 for track C. This is the highest number of submitted papers in the history of the ICALP conferences. The P- gram Committees selected 113 papers for inclusion in the scienti?c program. In particular, the Program Committee for track A selected 65 papers, the P- gram Committee for track B selected 24 papers, and the Program Committee for track C selected 24 papers. All the work of the Program Committees was done electronically.

Invited Lectures.- Holographic Circuits.- Probabilistic Polynomial-Time Semantics for a Protocol Security Logic.- A Gentle Introduction to Semantic Subtyping.- Logics for Unranked Trees: An Overview.- Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture.- Data Structures I.- The Tree Inclusion Problem: In Optimal Space and Faster.- Union-Find with Constant Time Deletions.- Optimal In-place Sorting of Vectors and Records.- Towards Optimal Multiple Selection.- Cryptography and Complexity.- Simple Extractors via Constructions of Cryptographic Pseudo-random Generators.- Bounds on the Efficiency of “Black-Box” Commitment Schemes.- On Round-Efficient Argument Systems.- Computational Bounds on Hierarchical Data Processing with Applications to Information Security.- Data Structures II.- Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins.- Worst Case Optimal Union-Intersection Expression Evaluation.- Measure and Conquer: Domination – A Case Study.- Cryptography and Distributed Systems.- Optimistic Asynchronous Atomic Broadcast.- Asynchronous Perfectly Secure Communication over One-Time Pads.- Single-Prover Concurrent Zero Knowledge in Almost Constant Rounds.- Graph Algorithms I.- LCA Queries in Directed Acyclic Graphs.- Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs.- Deterministic Constructions of Approximate Distance Oracles and Spanners.- An Õ(m 2 n) Randomized Algorithm to Compute a Minimum Cycle Basis of a Directed Graph.- Security Mechanisms.- Basing Cryptographic Protocols on Tamper-Evident Seals.- Hybrid Trapdoor Commitments and Their Applications.- On Steganographic Chosen Covertext Security.- Classification of Boolean Functions of 6 Variables or Less with Respect to Some Cryptographic Properties.- Graph Algorithms II.- Label-Guided Graph Exploration by a Finite Automaton.- On the Wake-Up Problem in Radio Networks.- Distance Constrained Labelings of Graphs of Bounded Treewidth.- Optimal Branch-Decomposition of Planar Graphs in O(n 3) Time.- Automata and Formal Languages I.- NFAs With and Without ?-Transitions.- On the Equivalence of -Automata.- A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata.- Groupoids That Recognize Only Regular Languages.- Signature and Message Authentication.- Append-Only Signatures.- Hierarchical Group Signatures.- Designated Verifier Signature Schemes: Attacks, New Security Notions and a New Construction.- Single-Key AIL-MACs from Any FIL-MAC.- Algorithmic Game Theory.- The Efficiency and Fairness of a Fixed Budget Resource Allocation Game.- Braess’s Paradox, Fibonacci Numbers, and Exponential Inapproximability.- Automata and Logic.- Weighted Automata and Weighted Logics.- Restricted Two-Variable FO + MOD Sentences, Circuits and Communication Complexity.- Computational Algebra.- Suitable Curves for Genus-4 HCC over Prime Fields: Point Counting Formulae for Hyperelliptic Curves of Type y 2=x +ax.- Solvability of a System of Bivariate Polynomial Equations over a Finite Field.- Cache-Oblivious Algorithms and Algorithmic Engineering.- Cache-Oblivious Planar Shortest Paths.- Cache-Aware and Cache-Oblivious Adaptive Sorting.- Simulated Annealing Beats Metropolis in Combinatorial Optimization.- On-line Algorithms.- Online Interval Coloring and Variants.- Dynamic Bin Packing of Unit Fractions Items.- Reordering Buffer Management for Non-uniform Cost Models.- Security Protocols Logic.- Combining Intruder Theories.- Computationally Sound Implementations of Equational Theories Against Passive Adversaries.- Password-Based Encryption Analyzed.- Random Graphs.- On the Cover Time of Random Geometric Graphs.- On the Existence of Hamiltonian Cycles in Random Intersection Graphs.- Optimal Cover Time for a Graph-Based Coupon Collector Process.- Stability and Similarity of Link Analysis Ranking Algorithms.- Concurrency I.- Up-to Techniques for Weak Bisimulation.- Petri Algebras.- A Finite Basis for Failure Semantics.- Spatial Logics for Bigraphs.- Encryption and related Primitives.- Completely Non-malleable Schemes.- Boneh-Franklin Identity Based Encryption Revisited.- Single-Database Private Information Retrieval with Constant Communication Rate.- Concurrent Zero Knowledge in the Public-Key Model.- Approximation Algorithms I.- A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines.- Polynomial Time Preemptive Sum-Multicoloring on Paths.- The Generalized Deadlock Resolution Problem.- Facility Location in Sublinear Time.- Games.- The Complexity of Stochastic Rabin and Streett Games.- Recursive Markov Decision Processes and Recursive Stochastic Games.- Decidability in Syntactic Control of Interference.- Idealized Algol with Ground Recursion, and DPDA Equivalence.- Approximation Algorithms II.- From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem.- How Well Can Primal-Dual and Local-Ratio Algorithms Perform?.- Approximating Max kCSP – Outperforming a Random Assignment with Almost a Linear Factor.- Lower Bounds.- On Dynamic Bit-Probe Complexity.- Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines.- Lower Bounds for Circuits with Few Modular and Symmetric Gates.- Probability.- Discrete Random Variables over Domains.- An Accessible Approach to Behavioural Pseudometrics.- Noisy Turing Machines.- Approximation Algorithms III.- A Better Approximation Ratio for the Vertex Cover Problem.- Stochastic Steiner Trees Without a Root.- Approximation Algorithms for the Max-coloring Problem.- Automata and Formal Languages II.- Tight Lower Bounds for Query Processing on Streaming and External Memory Data.- Decidability and Complexity Results for Timed Automata via Channel Machines.- Congruences for Visibly Pushdown Languages.- Approximation Algorithms IV.- Approximation Algorithms for Euclidean Group TSP.- Influential Nodes in a Diffusion Model for Social Networks.- An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks.- New Approaches for Virtual Private Network Design.- Algebraic Computation and Communication Complexity.- Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity.- Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.- On the l-Ary GCD-Algorithm in Rings of Integers.- Concurrency II.- A Fully Abstract Encoding of the ?-Calculus with Data Terms.- Orthogonal Extensions in Structural Operational Semantics.- Basic Observables for a Calculus for Global Computing.- Compositional Verification of Asynchronous Processes via Constraint Solving.- String Matching and Computational Biology.- Optimal Spaced Seeds for Faster Approximate String Matching.- Fast Neighbor Joining.- Randomized Fast Design of Short DNA Words.- Quantum Complexity.- A Quantum Lower Bound for the Query Complexity of Simon’s Problem.- All Quantum Adversary Methods Are Equivalent.- Quantum Complexity of Testing Group Commutativity.- Analysis and Verification.- Semantic-Based Code Obfuscation by Abstract Interpretation.- About Hoare Logics for Higher-Order Store.- The Polyranking Principle.- Geometry and Load Balancing.- Approximate Guarding of Monotone and Rectilinear Polygons.- Linear Time Algorithms for Clustering Problems in Any Dimensions.- Dynamic Diffusion Load Balancing.- Concrete Complexity and Codes.- On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group.- On the Hardness of Embeddings Between Two Finite Metrics.- Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval.- Model Theory and Model Checking.- Preservation Under Extensions on Well-Behaved Finite Structures.- Unsafe Grammars and Panic Automata.- Signaling P Systems and Verification Problems.