The two-volume set LNCS 6198 and LNCS 6199 constitutes the refereed proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP 2010, held in Bordeaux, France, in July 2010. The 106 revised full papers (60 papers for track A, 30 for track B, and 16 for track C) presented together with 6 invited talks were carefully reviewed and selected from a total of 389 submissions. The papers are grouped in three major tracks on algorithms, complexity and games; on logic, semantics, automata, and theory of programming; as well as on foundations of networked computation: models, algorithms and information management. LNCS 6198 contains 60 contributions of track A selected from 222 submissions as well as 2 invited talks.
Author(s): Burkhard Monien, Dominic Dumrauf, Tobias Tscheuschner (auth.), Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, Paul G. Spirakis (eds.)
Series: Lecture Notes in Computer Science 6198 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 754
Tags: Algorithm Analysis and Problem Complexity; Artificial Intelligence (incl. Robotics); Computation by Abstract Devices; Discrete Mathematics in Computer Science; Computer Communication Networks; Mathematical Logic and Formal Languages
Front Matter....Pages -
Local Search: Simple, Successful, But Sometimes Sluggish....Pages 1-17
When Conflicting Constraints Can Be Resolved – The Lovász Local Lemma and Satisfiability....Pages 18-18
Plane Spanners of Maximum Degree Six....Pages 19-30
The Positive Semidefinite Grothendieck Problem with Rank Constraint....Pages 31-42
Cycle Detection and Correction....Pages 43-54
Decomposition Width of Matroids....Pages 55-66
The Cooperative Game Theory Foundations of Network Bargaining Games....Pages 67-78
On the Existence of Pure Nash Equilibria in Weighted Congestion Games....Pages 79-89
On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions....Pages 90-101
Mean-Payoff Games and Propositional Proofs....Pages 102-113
Online Network Design with Outliers....Pages 114-126
Efficient Completely Non-malleable Public Key Encryption....Pages 127-139
Polynomial-Space Approximation of No-Signaling Provers....Pages 140-151
From Secrecy to Soundness: Efficient Verification via Secure Computation....Pages 152-163
Mergeable Dictionaries....Pages 164-175
Faster Algorithms for Semi-matching Problems (Extended Abstract)....Pages 176-187
Clustering with Diversity....Pages 188-200
New Data Structures for Subgraph Connectivity....Pages 201-212
Tight Thresholds for Cuckoo Hashing via XORSAT....Pages 213-225
Resource Oblivious Sorting on Multicores....Pages 226-237
Interval Sorting....Pages 238-249
Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems....Pages 250-261
Thresholded Covering Algorithms for Robust and Max-min Optimization....Pages 262-274
Graph Homomorphisms with Complex Values: A Dichotomy Theorem....Pages 275-286
Metrical Task Systems and the k -Server Problem on HSTs....Pages 287-298
Scheduling Periodic Tasks in a Hard Real-Time Environment....Pages 299-311
Scalably Scheduling Power-Heterogeneous Processors....Pages 312-323
Better Scalable Algorithms for Broadcast Scheduling....Pages 324-335
Max-min Online Allocations with a Reordering Buffer....Pages 336-347
Orientability of Random Hypergraphs and the Power of Multiple Choices....Pages 348-359
On the Inapproximability of Vertex Cover on k -Partite k -Uniform Hypergraphs....Pages 360-371
Dynamic Programming for Graphs on Surfaces....Pages 372-383
Interval Graphs: Canonical Representation in Logspace....Pages 384-395
Approximating the Partition Function of the Ferromagnetic Potts Model....Pages 396-407
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors....Pages 408-419
On Sums of Roots of Unity....Pages 420-425
Exponential Time Complexity of the Permanent and the Tutte Polynomial....Pages 426-437
On Approximate Horn Formula Minimization....Pages 438-450
Choosing, Agreeing, and Eliminating in Communication Complexity....Pages 451-462
Additive Spanners in Nearly Quadratic Time....Pages 463-474
Composition Theorems in Communication Complexity....Pages 475-489
Network Design via Core Detouring for Problems without a Core....Pages 490-502
Weak Completeness Notions for Exponential Time....Pages 503-514
Efficient Evaluation of Nondeterministic Automata Using Factorization Forests....Pages 515-526
On the Complexity of Searching in Trees: Average-Case Minimization....Pages 527-539
Finding Is as Easy as Detecting for Quantum Walks....Pages 540-551
Improved Constructions for Non-adaptive Threshold Group Testing....Pages 552-564
Testing Non-uniform k -Wise Independent Distributions over Product Spaces....Pages 565-581
A Sublogarithmic Approximation for Highway and Tollbooth Pricing....Pages 582-593
Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm....Pages 594-604
Cell Probe Lower Bounds and Approximations for Range Mode....Pages 605-616
SDP Gaps for 2-to-1 and Other Label-Cover Variants....Pages 617-628
Data Stream Algorithms for Codeword Testing....Pages 629-640
Streaming Algorithms for Independent Sets....Pages 641-652
Preprocessing of Min Ones Problems: A Dichotomy....Pages 653-665
Holographic Reduction: A Domain Changed Application and Its Partial Converse Theorems....Pages 666-677
Optimal Trade-Offs for Succinct String Indexes....Pages 678-689
Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems....Pages 690-701
Concurrent Knowledge Extraction in the Public-Key Model....Pages 702-714
On the k -Independence Required by Linear Probing and Minwise Independence....Pages 715-726
Covering and Packing in Linear Space....Pages 727-737
Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s - t Paths in Digraphs....Pages 738-749
Back Matter....Pages -
