Algebraic Complexity Theory

AvPeter Bürgisser,Michael Clausen

Häftad, Engelska, 2010

Del 315 i serien Grundlehren der mathematischen Wissenschaften

1 485 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt över 249 kr.

Fler format och utgåvor

Inbunden

1 485 kr

Skickas inom 10-15 vardagar

Beskrivning

This is the first book to present an up-to-date and self-contained account of Algebraic Complexity Theory that is both comprehensive and unified. Requiring of the reader only some basic algebra and offering over 350 exercises, it is well-suited as a textbook for beginners at graduate level. With its extensive bibliography covering about 500 research papers, this text is also an ideal reference book for the professional researcher. The subdivision of the contents into 21 more or less independent chapters enables readers to familiarize themselves quickly with a specific topic, and facilitates the use of this book as a basis for complementary courses in other areas such as computer algebra.

Produktinformation

Utgivningsdatum:2010-12-05
Mått:155 x 235 x 40 mm
Vikt:976 g
Format:Häftad
Språk:Engelska
Serie:Grundlehren der mathematischen Wissenschaften
Antal sidor:618
Förlag:Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
ISBN:9783642082283

Utforska kategorier

Recensioner i media

P. Burgisser, M. Clausen, M.A. Shokrollahi, and T. Lickteig Algebraic Complexity Theory "The book contains interesting exercises and useful bibliographical notes. In short, this is a nice book."-MATHEMATICAL REVIEWS From the reviews: "This book is certainly the most complete reference on algebraic complexity theory that is available hitherto. ... superb bibliographical and historical notes are given at the end of each chapter. ... this book would most certainly make a great textbook for a graduate course on algebraic complexity theory. ... In conclusion, any researchers already working in the area should own a copy of this book. ... beginners at the graduate level who have been exposed to undergraduate pure mathematics would find this book accessible." (Anthony Widjaja, SIGACT News, Vol. 37 (2), 2006)

Innehållsförteckning

1. Introduction.- I. Fundamental Algorithms.- 2. Efficient Polynomial Arithmetic.- 3. Efficient Algorithms with Branching.- II. Elementary Lower Bounds.- 4. Models of Computation.- 5. Preconditioning and Transcendence Degree.- 6. The Substitution Method.- 7. Differential Methods.- III. High Degree.- 8. The Degree Bound.- 9. Specific Polynomials which Are Hard to Compute.- 10. Branching and Degree.- 11. Branching and Connectivity.- 12. Additive Complexity.- IV. Low Degree.- 13. Linear Complexity.- 14. Multiplicative and Bilinear Complexity.- 15. Asymptotic Complexity of Matrix Multiplication.- 16. Problems Related to Matrix Multiplication.- 17. Lower Bounds for the Complexity of Algebras.- 18. Rank over Finite Fields and Codes.- 19. Rank of 2-Slice and 3-Slice Tensors.- 20. Typical Tensorial Rank.- V. Complete Problems.- 21. P Versus NP: A Nonuniform Algebraic Analogue.- List of Notation.