Automata, Languages and Programming 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I - Paperback

EAN (ISBN-13): 9783642141645
ISBN (ISBN-10): 3642141641
Hardcover
Paperback
Publishing year: 2010
Publisher: Abramsky, Samson, Gavoille, Cyril, Kirchner, Claude, Meyer auf der Heide, Friedhelm, Spirakis, Paul, Springer
754 Pages
Weight: 1,091 kg
Language: eng/Englisch

Book in our database since 2010-11-01T19:58:11+00:00 (London)
Detail page last modified on 2024-03-12T15:46:28+00:00 (London)
ISBN/EAN: 9783642141645

ISBN - alternate spelling:
3-642-14164-1, 978-3-642-14164-5
Alternate spelling and related search-keywords:
Book author: paul von der heide, kirchner, abrams, spira, spir, abram, samson, auf der, claude, bordeaux, jean meyer, paul burkhard, meyer pierre, friedhelm stöck, abramsky
Book title: rög, bordeaux, programming language, languages, international colloquium, lecture notes computer science automata, book programming

---

Information from Publisher

Author: Samson Abramsky; Cyril Gavoille; Claude Kirchner; Friedhelm Meyer auf der Heide; Paul Spirakis
Title: Theoretical Computer Science and General Issues; Lecture Notes in Computer Science; Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I
Publisher: Springer; Springer Berlin
754 Pages
Publishing year: 2010-06-30
Berlin; Heidelberg; DE
Language: English
106,99 € (DE)
109,99 € (AT)
118,00 CHF (CH)
Available
XXIII, 754 p. 42 illus.

BC; Hardcover, Softcover / Informatik, EDV/Informatik; Software Engineering; Verstehen; C programming language; Rack; algorithms; complexity; logic; programming; algorithm analysis and problem complexity; Software Engineering; Programming Techniques; Computer Communication Networks; Algorithms; Artificial Intelligence; Theory of Computation; Computerprogrammierung und Softwareentwicklung; Netzwerk-Hardware; Algorithmen und Datenstrukturen; Künstliche Intelligenz; Theoretische Informatik; EA

Invited Talks.- Local Search: Simple, Successful, But Sometimes Sluggish.- When Conflicting Constraints Can Be Resolved – The Lovász Local Lemma and Satisfiability.- Session 1-Track A. Combinatorial Optimization.- Plane Spanners of Maximum Degree Six.- The Positive Semidefinite Grothendieck Problem with Rank Constraint.- Cycle Detection and Correction.- Decomposition Width of Matroids.- Session 2-Track A1. Game Theory.- The Cooperative Game Theory Foundations of Network Bargaining Games.- On the Existence of Pure Nash Equilibria in Weighted Congestion Games.- On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions.- Mean-Payoff Games and Propositional Proofs.- Session 2-Track A2. Security.- Online Network Design with Outliers.- Efficient Completely Non-malleable Public Key Encryption.- Polynomial-Space Approximation of No-Signaling Provers.- From Secrecy to Soundness: Efficient Verification via Secure Computation.- Session 3-Track A1. Data Structures.- Mergeable Dictionaries.- Faster Algorithms for Semi-matching Problems (Extended Abstract).- Clustering with Diversity.- New Data Structures for Subgraph Connectivity.- Session 3-Track A2. Sorting & Hashing.- Tight Thresholds for Cuckoo Hashing via XORSAT.- Resource Oblivious Sorting on Multicores.- Interval Sorting.- Session 4-Track A. Graphs, Nets and Optimization.- Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems.- Thresholded Covering Algorithms for Robust and Max-min Optimization.- Graph Homomorphisms with Complex Values: A Dichotomy Theorem.- Metrical Task Systems and the k-Server Problem on HSTs.- Session 5-Track A1. Scheduling.- Scheduling Periodic Tasks in a Hard Real-Time Environment.- Scalably Scheduling Power-Heterogeneous Processors.- BetterScalable Algorithms for Broadcast Scheduling.- Max-min Online Allocations with a Reordering Buffer.- Session 5-Track A2. Graphs & Hypergraphs.- Orientability of Random Hypergraphs and the Power of Multiple Choices.- On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs.- Dynamic Programming for Graphs on Surfaces.- Interval Graphs: Canonical Representation in Logspace.- Session 6-Track A. Best Paper Award.- Approximating the Partition Function of the Ferromagnetic Potts Model.- Session 7-Track A. Algebraic Problems.- On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors.- On Sums of Roots of Unity.- Exponential Time Complexity of the Permanent and the Tutte Polynomial.- On Approximate Horn Formula Minimization.- Session 8-Track A. Networks & Communication Complexity.- Choosing, Agreeing, and Eliminating in Communication Complexity.- Additive Spanners in Nearly Quadratic Time.- Composition Theorems in Communication Complexity.- Network Design via Core Detouring for Problems without a Core.- Session 9-Track A1. Complexity & Automata.- Weak Completeness Notions for Exponential Time.- Efficient Evaluation of Nondeterministic Automata Using Factorization Forests.- On the Complexity of Searching in Trees: Average-Case Minimization.- Session 9-Track A2. Finding & Testing.- Finding Is as Easy as Detecting for Quantum Walks.- Improved Constructions for Non-adaptive Threshold Group Testing.- Testing Non-uniform k-Wise Independent Distributions over Product Spaces.- Session 10-Track A1. Approximations.- A Sublogarithmic Approximation for Highway and Tollbooth Pricing.- Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm.- Cell Probe Lower Bounds and Approximationsfor Range Mode.- SDP Gaps for 2-to-1 and Other Label-Cover Variants.- Session 10-Track A2. Streaming & Preprocessing.- Data Stream Algorithms for Codeword Testing.- Streaming Algorithms for Independent Sets.- Preprocessing of Min Ones Problems: A Dichotomy.- Holographic Reduction: A Domain Changed Application and Its Partial Converse Theorems.- Session 11-Track A1. Adaptive, Knowledge & Optimality.- Optimal Trade-Offs for Succinct String Indexes.- Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems.- Concurrent Knowledge Extraction in the Public-Key Model.- Session 11-Track A2. Covering, Graphs & Independence.- On the k-Independence Required by Linear Probing and Minwise Independence.- Covering and Packing in Linear Space.- Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs.