Automata, Languages and Programming: 34th International Colloquium, ICALP 2007, Wrocław, Poland, July 9-13, 2007. Proceedings

Front Matter....Pages -
Ushering in a New Era of Algorithm Design....Pages 1-1
A “proof-reading” of Some Issues in Cryptography....Pages 2-11
Credentials-Based Authorization: Evaluation and Implementation....Pages 12-14
Subexponential Parameterized Algorithms....Pages 15-27
Competitive Algorithms for Due Date Scheduling....Pages 28-39
Mechanism Design for Fractional Scheduling on Unrelated Machines....Pages 40-52
Estimating Sum by Weighted Sampling....Pages 53-64
Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima....Pages 65-77
Low Distortion Spanners....Pages 78-89
Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs....Pages 90-101
Labeling Schemes for Vertex Connectivity....Pages 102-109
Unbounded-Error One-Way Classical and Quantum Communication Complexity....Pages 110-121
A Lower Bound on Entanglement-Assisted Quantum Communication Complexity....Pages 122-133
Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity....Pages 134-145
An Optimal Decomposition Algorithm for Tree Edit Distance....Pages 146-157
On Commutativity Based Edge Lean Search....Pages 158-170
Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems....Pages 171-182
On the Complexity of Hard-Core Set Constructions....Pages 183-194
Approximation by DNF: Examples and Counterexamples....Pages 195-206
Exotic Quantifiers, Complexity Classes, and Complete Problems....Pages 207-218
Online Conflict-Free Colorings for Hypergraphs....Pages 219-230
Distributed Computing with Advice: Information Sensitivity of Graph Coloring....Pages 231-242
Private Multiparty Sampling and Approximation of Vector Combinations....Pages 243-254
Constant-Round Private Database Queries....Pages 255-266
Universal Algebra and Hardness Results for Constraint Satisfaction Problems....Pages 267-278
On the Power of k -Consistency....Pages 279-290
Complexity of Propositional Proofs Under a Promise....Pages 291-302
Deterministic History-Independent Strategies for Storing Information on Write-Once Memories....Pages 303-315
Trading Static for Adaptive Security in Universally Composable Zero-Knowledge....Pages 316-327
A Characterization of Non-interactive Instance-Dependent Commitment-Schemes (NIC)....Pages 328-339
Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs....Pages 340-351
Parameterized Algorithms for Directed Maximum Leaf Problems....Pages 352-362
Parameterized Approximability of the Disjoint Cycle Problem....Pages 363-374
Linear Problem Kernels for NP-Hard Problems on Planar Graphs....Pages 375-386
Private Locally Decodable Codes....Pages 387-398
Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms....Pages 399-410
Unrestricted Aggregate Signatures....Pages 411-422
Ring Signatures of Sub-linear Size Without Random Oracles....Pages 423-434
Balanced Families of Perfect Hash Functions and Their Applications....Pages 435-446
An Exponential Improvement on the MST Heuristic for Minimum Energy Broadcasting in Ad Hoc Wireless Networks....Pages 447-458
Modular Algorithms for Heterogeneous Modal Logics....Pages 459-471
Co-Logic Programming: Extending Logic Programming with Coinduction....Pages 472-483
Offline/Online Mixing....Pages 484-495
Fully Collusion Resistant Black-Box Traitor Revocable Broadcast Encryption with Short Private Keys....Pages 496-508
Succinct Ordinal Trees Based on Tree Covering....Pages 509-520
A Framework for Dynamizing Succinct Data Structures....Pages 521-532
In-Place Suffix Sorting....Pages 533-545
Maximal Infinite-Valued Constraint Languages....Pages 546-557
 Affine Systems of Equations and Counting Infinitary Logic ....Pages 558-570
Boundedness of Monadic FO over Acyclic Structures....Pages 571-582
Strong Price of Anarchy for Machine Load Balancing....Pages 583-594
Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games....Pages 595-606
Equational Systems and Free Constructions (Extended Abstract) ....Pages 607-618
Categorical Views on Computations on Trees (Extended Abstract)....Pages 619-630
Holographic Algorithms: The Power of Dimensionality Resolved....Pages 631-642
Reconciling Data Compression and Kolmogorov Complexity....Pages 643-654
Size Competitive Meshing Without Large Angles....Pages 655-666
A Fully Abstract Trace Semantics for General References....Pages 667-679
Aliased Register Allocation for Straight-Line Programs Is NP-Complete....Pages 680-691
Conservative Ambiguity Detection in Context-Free Grammars....Pages 692-703
Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming....Pages 704-715
Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners....Pages 716-727
Checking and Spot-Checking the Correctness of Priority Queues....Pages 728-739
Undecidability of 2-Label BPP Equivalences and Behavioral Type Systems for the π -Calculus....Pages 740-751
Ready Simulation for Concurrency: It’s Logical!....Pages 752-763
Continuous Capacities on Continuous State Spaces....Pages 764-776
On the Chromatic Number of Random Graphs....Pages 777-788
Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions....Pages 789-800
Complexity of the Cover Polynomial....Pages 801-812
A Generalization of Cobham’s Theorem to Automata over Real Numbers....Pages 813-824
Minimum-Time Reachability in Timed Games....Pages 825-837
Reachability-Time Games on Timed Automata....Pages 838-849
Perfect Information Stochastic Priority Games....Pages 850-861
Bounded Depth Data Trees....Pages 862-874
Unranked Tree Automata with Sibling Equalities and Disequalities....Pages 875-887
Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization....Pages 888-900
A Combinatorial Theorem for Trees....Pages 901-912
Model Theory Makes Formulas Large....Pages 913-924
Decision Problems for Lower/Upper Bound Parametric Timed Automata....Pages 925-936
On the Complexity of Ltl Model-Checking of Recursive State Machines....Pages 937-948
Paper Retraction: On the Hardness of Embeddings Between Two Finite Metrics....Pages 949-949
Back Matter....Pages -