Automata, Languages and Programming : 35th International Colloquium, ICALP 2008 Reykjavik, Iceland, July 7-11, 2008 Proceedings, Part I - neues Buch

EAN (ISBN-13): 9783540705758
ISBN (ISBN-10): 3540705759
Erscheinungsjahr: 2008
Herausgeber: Springer Berlin
23 Seiten
Sprache: eng/Englisch

Buch in der Datenbank seit 2009-02-02T22:57:24+01:00 (Zurich)
Detailseite zuletzt geändert am 2024-03-31T10:32:38+02:00 (Zurich)
ISBN/EAN: 9783540705758

ISBN - alternative Schreibweisen:
3-540-70575-9, 978-3-540-70575-8
Alternative Schreibweisen und verwandte Suchbegriffe:
Autor des Buches: goldberg ann, jim goldberg, ivan gold
Titel des Buches: art programming, programming language, automata, reykjavik, colloquium international, reykjavík

---

Daten vom Verlag:

Autor/in: Luca Aceto; Ivan Damgaard; Leslie Ann Goldberg; Magnus M. Halldorsson; Anna Ingolfsdottir; Igor Walukiewicz
Titel: Theoretical Computer Science and General Issues; Lecture Notes in Computer Science; Automata, Languages and Programming - 35th International Colloquium, ICALP 2008 Reykjavik, Iceland, July 7-11, 2008 Proceedings, Part I
Verlag: Springer; Springer Berlin
896 Seiten
Erscheinungsjahr: 2008-07-06
Berlin; Heidelberg; DE
Sprache: Englisch
149,79 € (DE)
154,00 € (AT)
193,50 CHF (CH)
Available
XXIII, 896 p.

EA; E107; eBook; Nonbooks, PBS / Informatik, EDV/Informatik; Software Engineering; Verstehen; algorithmic game theory; algorithms; complexity; data structures; design; logic; programming; scheduling; testing; C; Software Engineering; Programming Techniques; Theory of Computation; Discrete Mathematics in Computer Science; Numerical Analysis; Data Science; Computer Science; Computerprogrammierung und Softwareentwicklung; Theoretische Informatik; Mathematik für Informatiker; Diskrete Mathematik; Numerische Mathematik; Datenbanken; BC

Invited Lectures.- Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects.- Internet Ad Auctions: Insights and Directions.- Track A: Algorithms, Automata, Complexity, and Games.- The Complexity of Boolean Formula Minimization.- Optimal Cryptographic Hardness of Learning Monotone Functions.- On Berge Multiplication for Monotone Boolean Dualization.- Diagonal Circuit Identity Testing and Lower Bounds.- Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity.- Constructing Efficient Dictionaries in Close to Sorting Time.- On List Update with Locality of Reference.- A New Combinatorial Approach for Sparse Graph Problems.- How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs).- Networks Become Navigable as Nodes Move and Forget.- Fast Distributed Computation of Cuts Via Random Circulations.- Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time.- Function Evaluation Via Linear Programming in the Priced Information Model.- Improved Approximation Algorithms for Budgeted Allocations.- The Travelling Salesman Problem in Bounded Degree Graphs.- Treewidth Computation and Extremal Combinatorics.- Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines.- Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2.- A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation.- Optimal Monotone Encodings.- Polynomial-Time Construction of Linear Network Coding.- Complexity of Decoding Positive-Rate Reed-Solomon Codes.- Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract).- The Randomized Coloring Procedure with Symmetry-Breaking.- The Local Nature of List Colorings for Graphs of High Girth.- Approximating List-Coloring on a Fixed Surface.- Asymptotically Optimal Hitting Sets Against Polynomials.- The Smoothed Complexity of Edit Distance.- Randomized Self-assembly for Approximate Shapes.- Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract).- Competitive Weighted Matching in Transversal Matroids.- Scheduling for Speed Bounded Processors.- Faster Algorithms for Incremental Topological Ordering.- Dynamic Normal Forms and Dynamic Characteristic Polynomial.- Algorithms for ?-Approximations of Terrains.- An Approximation Algorithm for Binary Searching in Trees.- Algorithms for 2-Route Cut Problems.- The Two-Edge Connectivity Survivable Network Problem in Planar Graphs.- Efficiently Testing Sparse GF(2) Polynomials.- Testing Properties of Sets of Points in Metric Spaces.- An Expansion Tester for Bounded Degree Graphs.- Property Testing on k-Vertex-Connectivity of Graphs.- Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract).- On Problems without Polynomial Kernels (Extended Abstract).- Faster Algebraic Algorithms for Path and Packing Problems.- Understanding the Complexity of Induced Subgraph Isomorphisms.- Spanners in Sparse Graphs.- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error.- All-Pairs Shortest Paths with a Sublinear Additive Error.- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations.- The Complexity of the Counting Constraint Satisfaction Problem.- On the Hardness of Losing Weight.- Product Theorems Via Semidefinite Programming.- Sound 3-Query PCPPs Are Long.- Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations.- Recursive Stochastic Games with Positive Rewards.- Complementation, Disambiguation, andDeterminization of Büchi Automata Unified.- Tree Projections: Hypergraph Games and Minimality.- Explicit Non-adaptive Combinatorial Group Testing Schemes.- Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination.- Impossibility of a Quantum Speed-Up with a Faulty Oracle.- Superpolynomial Speedups Based on Almost Any Quantum Circuit.- The Speed of Convergence in Congestion Games under Best-Response Dynamics.- Uniform Budgets and the Envy-Free Pricing Problem.- Bayesian Combinatorial Auctions.- Truthful Unification Framework for Packing Integer Programs with Choices.- Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing.- Finding Optimal Flows Efficiently.- Optimal Quantum Adversary Lower Bounds for Ordered Search.- Quantum SAT for a Qutrit-Cinquit Pair Is QMA 1-Complete.- Superpolynomial Speedups Based on Almost Any Quantum Circuit.