Overview

Full Product Details

Author:   Volker Diekert ,  Bruno Durand
Publisher:   Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint:   Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Edition:   2005 ed.
Volume:   3404
Dimensions:   Width: 15.50cm , Height: 3.60cm , Length: 23.50cm
Weight:   2.210kg
ISBN:  

9783540249986

ISBN 10:   3540249982
Pages:   706
Publication Date:   16 February 2005
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.

Table of Contents

Invited Talks.- Automorphisms of Finite Rings and Applications to Complexity of Problems.- Algebraic Generating Functions in Enumerative Combinatorics and Context-Free Languages.- Algorithmics in Exponential Time.- Session 1A.- Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics.- Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms.- Truthful Approximation Mechanisms for Scheduling Selfish Related Machines.- Session 1B.- Counting in the Two Variable Guarded Logic with Transitivity.- The Variable Hierarchy of the ?-Calculus Is Strict.- The Core of a Countably Categorical Structure.- Session 2A.- How Common Can Be Universality for Cellular Automata?.- Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods.- Session 2B.- On the Decidability of Temporal Properties of Probabilistic Pushdown Automata.- Deciding Properties of Contract-Signing Protocols.- Session 3A.- Polylog-Time Reductions Decrease Dot-Depth.- On the Computational Complexity of the Forcing Chromatic Number.- More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP.- Session 3B.- Three Optimal Algorithms for Balls of Three Colors.- Cost Sharing and Strategyproof Mechanisms for Set Cover Games.- On Weighted Balls-into-Bins Games.- Session 4A.- Computing Minimal Multi-homogeneous Bézout Numbers Is Hard.- Dynamic Complexity Theory Revisited.- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size.- Session 4B.- Shortest Monotone Descent Path Problem in Polyhedral Terrain.- Packet Buffering: Randomization Beats Deterministic Algorithms.- Solving Medium-Density Subset Sum Problems in Expected Polynomial Time.- Session 5A.- Quantified Constraint Satisfaction, MaximalConstraint Languages, and Symmetric Polymorphisms.- Regular Tree Languages Definable in FO.- Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations.- Session 5B.- Connectivity for Wireless Agents Moving on a Cycle or Grid.- Improved Algorithms for Dynamic Page Migration.- Approximate Range Mode and Range Median Queries.- Session 6A.- Topological Automata.- Minimizing NFA’s and Regular Expressions.- Session 6B.- Increasing Kolmogorov Complexity.- Kolmogorov-Loveland Randomness and Stochasticity.- Session 7A.- Information Theory in Property Testing and Monotonicity Testing in Higher Dimension.- On Nash Equilibria in Non-cooperative All-Optical Networks.- Speed Scaling to Manage Temperature.- Session 7B.- The Complexity of Solving Linear Equations over a Finite Ring.- A Lower Bound on the Complexity of Polynomial Multiplication Over Finite Fields.- Characterizing TC0 in Terms of Infinite Groups.- Session 8A.- Fast Pruning of Geometric Spanners.- The PIGs Full Monty – A Floor Show of Minimal Separators.- Centrality Measures Based on Current Flow.- Session 8B.- Varieties of Codes and Kraft Inequality.- Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes.- The Power of Commuting with Finite Sets of Words.- Session 9A.- Exact Quantum Algorithms for the Leader Election Problem.- Robust Polynomials and Quantum Algorithms.- Quantum Interactive Proofs with Competing Provers.- Session 9B.- Roundings Respecting Hard Constraints.- Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves.- Cycle Cover with Short Cycles.- Session 10A.- A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs.- All-Pairs Nearly 2-Approximate Shortest-Paths in O(n 2 polylog n) Time.- Session 10B.- PatternOccurrences in Multicomponent Models.- Automatic Presentations for Finitely Generated Groups.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions