Overview

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.

Full Product Details

Author:   T. Lickteig ,  Peter Bürgisser ,  Michael Clausen ,  Mohammad A. Shokrollahi
Publisher:   Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint:   Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Edition:   1997 ed.
Volume:   315
Dimensions:   Width: 15.50cm , Height: 3.40cm , Length: 23.50cm
Weight:   2.390kg
ISBN:  

9783540605829

ISBN 10:   3540605827
Pages:   618
Publication Date:   16 December 1996
Audience:   College/higher education ,  Professional and scholarly ,  Undergraduate ,  Postgraduate, Research & Scholarly
Format:   Hardback
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

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.

Reviews

P. BA1/4rgisser, M. Clausen, M.A. Shokrollahi, and T. Lickteig <p>Algebraic Complexity Theory <p> The book contains interesting exercises and useful bibliographical notes. In short, this is a nice book. a MATHEMATICAL REVIEWS <p>From the reviews: <p> This book is certainly the most complete reference on algebraic complexity theory that is available hitherto. a ] superb bibliographical and historical notes are given at the end of each chapter. a ] this book would most certainly make a great textbook for a graduate course on algebraic complexity theory. a ] In conclusion, any researchers already working in the area should own a copy of this book. a ] 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)

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)

Author Information

Tab Content 6

Author Website:  

Countries Available

All regions