Algebraic complexity theory
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...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | Book |
| Language: | English |
| Published: |
Berlin, Germany
Springer
1997
|
| Series: | Grundlehren der mathematischen Wissenschaften
315 |
| Subjects: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- Ch. 1. Introduction
- Ch. 2. Efficient Polynomial Arithmetic
- Ch. 3. Efficient Algorithms with Branching
- Ch. 4. Models of Computation
- Ch. 5. Preconditioning and Transcendence Degree
- Ch. 6. The Substitution Method
- Ch. 7. Differential Methods
- Ch. 8. The Degree Bound
- Ch. 9. Specific Polynomials which Are Hard to Compute
- Ch. 10. Branching and Degree
- Ch. 11. Branching and Connectivity
- Ch. 12. Additive Complexity
- Ch. 13. Linear Complexity
- Ch. 14. Multiplicative and Bilinear Complexity
- Ch. 15. Asymptotic Complexity of Matrix Multiplication
- Ch. 16. Problems Related to Matrix Multiplication
- Ch. 17. Lower Bounds for the Complexity of Algebras
- Ch. 18. Rank over Finite Fields and Codes
- Ch. 19. Rank of 2-Slice and 3-Slice Tensors
- Ch. 20. Typical Tensorial Rank
- Ch. 21. P Versus NP: A Nonuniform Algebraic Analogue.