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

Leslie G. Valiant (auth.), Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi, Moti Yung (eds.)3540275800, 9783540275800

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.

---

Table of contents :
Front Matter….Pages –
Holographic Circuits….Pages 1-15
Probabilistic Polynomial-Time Semantics for a Protocol Security Logic….Pages 16-29
A Gentle Introduction to Semantic Subtyping….Pages 30-34
Logics for Unranked Trees: An Overview….Pages 35-50
Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture….Pages 51-65
The Tree Inclusion Problem: In Optimal Space and Faster….Pages 66-77
Union-Find with Constant Time Deletions….Pages 78-89
Optimal In-place Sorting of Vectors and Records….Pages 90-102
Towards Optimal Multiple Selection….Pages 103-114
Simple Extractors via Constructions of Cryptographic Pseudo-random Generators….Pages 115-127
Bounds on the Efficiency of “Black-Box” Commitment Schemes….Pages 128-139
On Round-Efficient Argument Systems….Pages 140-152
Computational Bounds on Hierarchical Data Processing with Applications to Information Security….Pages 153-165
Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins….Pages 166-178
Worst Case Optimal Union-Intersection Expression Evaluation….Pages 179-190
Measure and Conquer: Domination – A Case Study….Pages 191-203
Optimistic Asynchronous Atomic Broadcast….Pages 204-215
Asynchronous Perfectly Secure Communication over One-Time Pads….Pages 216-227
Single-Prover Concurrent Zero Knowledge in Almost Constant Rounds….Pages 228-240
LCA Queries in Directed Acyclic Graphs….Pages 241-248
Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs….Pages 249-260
Deterministic Constructions of Approximate Distance Oracles and Spanners….Pages 261-272
An Õ ( m 2 n ) Randomized Algorithm to Compute a Minimum Cycle Basis of a Directed Graph….Pages 273-284
Basing Cryptographic Protocols on Tamper-Evident Seals….Pages 285-297
Hybrid Trapdoor Commitments and Their Applications….Pages 298-310
On Steganographic Chosen Covertext Security….Pages 311-323
Classification of Boolean Functions of 6 Variables or Less with Respect to Some Cryptographic Properties….Pages 324-334
Label-Guided Graph Exploration by a Finite Automaton….Pages 335-346
On the Wake-Up Problem in Radio Networks….Pages 347-359
Distance Constrained Labelings of Graphs of Bounded Treewidth….Pages 360-372
Optimal Branch-Decomposition of Planar Graphs in O ( n 3 ) Time….Pages 373-384
NFAs With and Without ε -Transitions….Pages 385-396
On the Equivalence of ${mathbb Z}$ -Automata….Pages 397-409
A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata….Pages 410-420
Groupoids That Recognize Only Regular Languages….Pages 421-433
Append-Only Signatures….Pages 434-445
Hierarchical Group Signatures….Pages 446-458
Designated Verifier Signature Schemes: Attacks, New Security Notions and a New Construction….Pages 459-471
Single-Key AIL-MACs from Any FIL-MAC….Pages 472-484
The Efficiency and Fairness of a Fixed Budget Resource Allocation Game….Pages 485-496
Braess’s Paradox, Fibonacci Numbers, and Exponential Inapproximability….Pages 497-512
Weighted Automata and Weighted Logics….Pages 513-525
Restricted Two-Variable FO + MOD Sentences, Circuits and Communication Complexity….Pages 526-538
Suitable Curves for Genus-4 HCC over Prime Fields: Point Counting Formulae for Hyperelliptic Curves of Type y 2 = x $^{rm 2{it k}+1}$ + ax ….Pages 539-550
Solvability of a System of Bivariate Polynomial Equations over a Finite Field….Pages 551-562
Cache-Oblivious Planar Shortest Paths….Pages 563-575
Cache-Aware and Cache-Oblivious Adaptive Sorting….Pages 576-588
Simulated Annealing Beats Metropolis in Combinatorial Optimization….Pages 589-601
Online Interval Coloring and Variants….Pages 602-613
Dynamic Bin Packing of Unit Fractions Items….Pages 614-626
Reordering Buffer Management for Non-uniform Cost Models….Pages 627-638
Combining Intruder Theories….Pages 639-651
Computationally Sound Implementations of Equational Theories Against Passive Adversaries….Pages 652-663
Password-Based Encryption Analyzed….Pages 664-676
On the Cover Time of Random Geometric Graphs….Pages 677-689
On the Existence of Hamiltonian Cycles in Random Intersection Graphs….Pages 690-701
Optimal Cover Time for a Graph-Based Coupon Collector Process….Pages 702-716
Stability and Similarity of Link Analysis Ranking Algorithms….Pages 717-729
Up-to Techniques for Weak Bisimulation….Pages 730-741
Petri Algebras….Pages 742-754
A Finite Basis for Failure Semantics….Pages 755-765
Spatial Logics for Bigraphs….Pages 766-778
Completely Non-malleable Schemes….Pages 779-790
Boneh-Franklin Identity Based Encryption Revisited….Pages 791-802
Single-Database Private Information Retrieval with Constant Communication Rate….Pages 803-815
Concurrent Zero Knowledge in the Public-Key Model….Pages 816-827
A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines….Pages 828-839
Polynomial Time Preemptive Sum-Multicoloring on Paths….Pages 840-852
The Generalized Deadlock Resolution Problem….Pages 853-865
Facility Location in Sublinear Time….Pages 866-877
The Complexity of Stochastic Rabin and Streett Games….Pages 878-890
Recursive Markov Decision Processes and Recursive Stochastic Games….Pages 891-903
Decidability in Syntactic Control of Interference….Pages 904-916
Idealized Algol with Ground Recursion, and DPDA Equivalence….Pages 917-929
From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem….Pages 930-942
How Well Can Primal-Dual and Local-Ratio Algorithms Perform?….Pages 943-955
Approximating Max k CSP – Outperforming a Random Assignment with Almost a Linear Factor….Pages 956-968
On Dynamic Bit-Probe Complexity….Pages 969-981
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines….Pages 982-993
Lower Bounds for Circuits with Few Modular and Symmetric Gates….Pages 994-1005
Discrete Random Variables over Domains….Pages 1006-1017
An Accessible Approach to Behavioural Pseudometrics….Pages 1018-1030
Noisy Turing Machines….Pages 1031-1042
A Better Approximation Ratio for the Vertex Cover Problem….Pages 1043-1050
Stochastic Steiner Trees Without a Root….Pages 1051-1063
Approximation Algorithms for the Max-coloring Problem….Pages 1064-1075
Tight Lower Bounds for Query Processing on Streaming and External Memory Data….Pages 1076-1088
Decidability and Complexity Results for Timed Automata via Channel Machines….Pages 1089-1101
Congruences for Visibly Pushdown Languages….Pages 1102-1114
Approximation Algorithms for Euclidean Group TSP….Pages 1115-1126
Influential Nodes in a Diffusion Model for Social Networks….Pages 1127-1138
An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks….Pages 1139-1150
New Approaches for Virtual Private Network Design….Pages 1151-1162
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity….Pages 1163-1175
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity….Pages 1176-1188
On the l -Ary GCD-Algorithm in Rings of Integers….Pages 1189-1201
A Fully Abstract Encoding of the π -Calculus with Data Terms….Pages 1202-1213
Orthogonal Extensions in Structural Operational Semantics….Pages 1214-1225
Basic Observables for a Calculus for Global Computing….Pages 1226-1238
Compositional Verification of Asynchronous Processes via Constraint Solving….Pages 1239-1250
Optimal Spaced Seeds for Faster Approximate String Matching….Pages 1251-1262
Fast Neighbor Joining….Pages 1263-1274
Randomized Fast Design of Short DNA Words….Pages 1275-1286
A Quantum Lower Bound for the Query Complexity of Simon’s Problem….Pages 1287-1298
All Quantum Adversary Methods Are Equivalent….Pages 1299-1311
Quantum Complexity of Testing Group Commutativity….Pages 1312-1324
Semantic-Based Code Obfuscation by Abstract Interpretation….Pages 1325-1336
About Hoare Logics for Higher-Order Store….Pages 1337-1348
The Polyranking Principle….Pages 1349-1361
Approximate Guarding of Monotone and Rectilinear Polygons….Pages 1362-1373
Linear Time Algorithms for Clustering Problems in Any Dimensions….Pages 1374-1385
Dynamic Diffusion Load Balancing….Pages 1386-1398
On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group….Pages 1399-1411
On the Hardness of Embeddings Between Two Finite Metrics….Pages 1412-1423
Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval….Pages 1424-1436
Preservation Under Extensions on Well-Behaved Finite Structures….Pages 1437-1449
Unsafe Grammars and Panic Automata….Pages 1450-1461
Signaling P Systems and Verification Problems….Pages 1462-1473
Back Matter….Pages –