Algebraic Complexity Theory

Algebraic Complexity Theory by Peter Bürgisser, Michael Clausen, Mohammad A. Shokrollahi.

The algorithmic solution of problems has always been one of the major concerns of mathematics. For a long time such solutions were based on an intuitive notion of algorithm. It is only in this century that metamathematical problems have led to the intensive search for a precise and sufficiently gene...

Full description

Saved in:
Bibliographic Details
Main Authors: Bürgisser, Peter (Author), Clausen, Michael (Author), Shokrollahi, Mohammad A. (Author)
Corporate Author: SpringerLink (Online service)
Format: eBook
Language:English
Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1997.
Edition:1st ed. 1997.
Series:Grundlehren der mathematischen Wissenschaften, A Series of Comprehensive Studies in Mathematics, 315
Springer eBook Collection.
Subjects:
Combinatorics.
Computers.
Mathematical logic.
Algorithms.
Algebraic geometry.
Electronic resources (E-books)
Online Access:Click to view e-book
Holy Cross Note:Loaded electronically.
Electronic access restricted to members of the Holy Cross Community.
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.

Similar Items