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

EAN (ISBN-13): 9783642141645
ISBN (ISBN-10): 3642141641
Version reliée
Livre de poche
Date de parution: 2010
Editeur: Abramsky, Samson, Gavoille, Cyril, Kirchner, Claude, Meyer auf der Heide, Friedhelm, Spirakis, Paul, Springer
754 Pages
Poids: 1,091 kg
Langue: eng/Englisch

Livre dans la base de données depuis 2010-11-01T20:58:11+01:00 (Zurich)
Page de détail modifiée en dernier sur 2024-03-12T16:46:28+01:00 (Zurich)
ISBN/EAN: 9783642141645

ISBN - Autres types d'écriture:
3-642-14164-1, 978-3-642-14164-5
Autres types d'écriture et termes associés:
Auteur du livre: paul von der heide, kirchner, abrams, spira, spir, abram, samson, auf der, claude, bordeaux, jean meyer, paul burkhard, meyer pierre, friedhelm stöck, abramsky
Titre du livre: rög, bordeaux, programming language, languages, international colloquium, lecture notes computer science automata, book programming

---

Données de l'éditeur

Auteur: Samson Abramsky; Cyril Gavoille; Claude Kirchner; Friedhelm Meyer auf der Heide; Paul Spirakis
Titre: 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
Editeur: Springer; Springer Berlin
754 Pages
Date de parution: 2010-06-30
Berlin; Heidelberg; DE
Langue: Anglais
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.