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

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 -