Bernard Chazelle (auth.), Lars Arge, Christian Cachin, Tomasz Jurdziński, Andrzej Tarlecki (eds.)3540734198, 9783540734192
Seventy-six full papers are presented, together with four invited lectures. Each paper, submitted by an expert in the field, was carefully reviewed to ensure that all the papers in this volume are accurate, thorough, and easy to follow. The papers are grouped into three major tracks covering algorithms, automata, complexity, and games; logic, semantics, and theory of programming; and security and cryptography foundations.
Readers will discover important new research findings and applications in the field.
Table of contents :
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 –
Reviews
There are no reviews yet.