Christos H. Papadimitriou (auth.), Fernando Orejas, Paul G. Spirakis, Jan van Leeuwen (eds.)3540422870, 9783540422877
The 80 revised papers presented together with two keynote contributions and four invited papers were carefully reviewed and selected from a total of 208 submissions. The papers are organized in topical sections on algebraic and circuit complexity, algorithm analysis, approximation and optimization, complexity, concurrency, efficient data structures, graph algorithms, language theory, codes and automata, model checking and protocol analysis, networks and routing, reasoning and verification, scheduling, secure computation, specification and deduction, and structural complexity.
Table of contents :
Algorithms, Games, and the Internet….Pages 1-3
Automata, Circuits, and Hybrids: Facets of Continuous Time….Pages 4-23
Languages, Rewriting Systems, and Verification of Infinite-State Systems….Pages 24-39
Integrating Semantics for Object—Oriented System Models….Pages 40-60
Modelling with Partial Orders — Why and Why Not?….Pages 61-63
Theoretical Aspects of Evolutionary Algorithms….Pages 64-78
Improvements of the Alder—Strassen Bound: Algebras with Nonzero Radical….Pages 79-91
On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities….Pages 92-103
Division Is In Uniform TC 0 ….Pages 104-114
A Framework for Index Bulk Loading and Dynamization….Pages 115-127
A Characterization of Temporal Locality and Its Portability across Memory Hierarchies….Pages 128-139
The Complexity of Constructing Evolutionary Trees Using Experiments….Pages 140-151
Hidden Pattern Statistics….Pages 152-165
Combinatorics and Algorithms on Low-Discrepancy Roundings of a Real Sequence….Pages 166-177
All-Pairs Shortest Paths Computation in the BSP Model….Pages 178-189
Approximating the Minimum Spanning Tree Weight in Sublinear Time….Pages 190-200
Approximation Hardness of TSP with Bounded Metrics….Pages 201-212
The RPR 2 Rounding Technique for Semidefinite Programs….Pages 213-224
Approximation Algorithms for Partial Covering Problems….Pages 225-236
On the Online Bin Packing Problem….Pages 237-248
Quick k -Median, k -Center, and Facility Location for Sparse Graphs….Pages 249-260
Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems….Pages 261-272
Subexponential Parameterized Algorithms Collapse the W-Hierarchy….Pages 273-284
Improved Lower Bounds on the Randomized Complexity of Graph Properties….Pages 285-296
New Imperfect Random Source with Applications to Coin-Flipping….Pages 297-309
Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently….Pages 310-321
Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations….Pages 322-333
On Interactive Proofs with a Laconic Prover….Pages 334-345
Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness….Pages 346-357
Lower Bounds in the Quantum Cell Probe Model….Pages 358-369
Axiomatizations for Probabilistic Bisimulation….Pages 370-381
Noninterference for Concurrent Programs….Pages 382-395
Distributed Controller Synthesis for Local Specifications….Pages 396-407
A Distributed Abstract Machine for Safe Ambients….Pages 408-420
Towards Quantitative Verification of Probabilistic Transition Systems….Pages 421-432
Efficient Generation of Plane Triangulations without Repetitions….Pages 433-443
The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations….Pages 444-455
Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher….Pages 456-468
A New Method for Balancing Binary Search Trees….Pages 469-480
Permutation Editing and Matching via Embeddings….Pages 481-492
Testing Hypergraph Coloring….Pages 493-505
Total Colorings of Degenerated Graphs….Pages 506-517
Decidable Properties of Graphs of All-Optical Networks….Pages 518-529
Majority Consensus and the Local Majority Rule….Pages 530-542
Solvability of Equations in Free Partially Commutative Groups Is decidable….Pages 543-554
Rational Transformations of Formal Power Series….Pages 555-566
Combinatorics of Three-Interval Exchanges….Pages 567-578
Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages….Pages 579-590
The Star Problem in Trace Monoids: Reductions Beyond C4….Pages 591-602
The Trace Coding Problem Is Undecidable….Pages 603-614
Combinatorics of Periods in Strings….Pages 615-626
Minimal Tail-Biting Trellises for Certain Cyclic Block Codes Are Easy to Construct….Pages 627-638
Effective Lossy Queue Languages….Pages 639-651
Model Checking of Unrestricted Hierarchical State Machines….Pages 652-666
Symbolic Trace Analysis of Cryptographic Protocols….Pages 667-681
Tree Automata with One Memory, Set Constraints, and Ping-Pong Protocols….Pages 682-693
Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata….Pages 694-707
Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width….Pages 708-719
From Finite State Communication Protocols to High-Level Message Sequence Charts….Pages 720-731
Fractional Path Coloring with Applications to WDM Networks….Pages 732-743
Performance Aspects of Distributed Caches Using TTL-Based Consistency….Pages 744-756
Routing in Trees….Pages 757-772
Online Packet Routing on Linear Arrays and Rings….Pages 773-784
Faster Gossiping on Butterflies….Pages 785-796
Realizability and Verification of MSC Graphs….Pages 797-808
Reasoning about Sequential and Branching Behaviours of Message Sequence Graphs….Pages 809-820
A Set-Theoretic Framework for Assume-Guarantee Reasoning….Pages 821-834
Foundations for Circular Compositional Reasoning….Pages 835-847
A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines….Pages 848-861
The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts….Pages 862-874
On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates….Pages 875-886
On the Approximability of Average Completion Time Scheduling under Precedence Constraints….Pages 887-897
Optimistic Asynchronous Multi-party Contract Signing with Reduced Number of Rounds….Pages 898-911
Information-Theoretic Private Information Retrieval: A Unified Construction….Pages 912-926
Secure Multiparty Computation of Approximations….Pages 927-938
Secure Games with Polynomial Expressions….Pages 939-950
On the Completeness of Arbitrary Selection Strategies for Paramodulation….Pages 951-962
An Axiomatic Approach to Metareasoning on Nominal Algebras in HOAS….Pages 963-978
Knuth-Bendix Constraint Solving Is NP-Complete….Pages 979-992
Amalgamation in CASL via Enriched Signatures….Pages 993-1004
Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution….Pages 1005-1016
Time and Space Bounds for Reversible Simulation….Pages 1017-1027
Finite-State Dimension….Pages 1028-1039
The Complexity of Computing the Size of an Interval….Pages 1040-1051
Communication Gap for Finite Memory Devices….Pages 1052-1064
Separating Quantum and Classical Learning….Pages 1065-1080
Reviews
There are no reviews yet.