Chapter 1.Introduction
1.1 Exercises
1.2 Open Problems
1.3 Notes
PartⅠ.Fundamental Algorithms
Chapter 2. Efficient Polynomial Arithmetic
2.1 Multiplication of Polynomials I
2.2* Multiplication of Polynomials II
2.3* Multiplication of Several Polynomials
2.4 Multiplication and Inversion of Power Series
2.5* Composition of Power Series
2.6 Exercises
2.7 Open Problems
2.8 Notes
Chapter 3. Efficient Algorithms with Branching
3.1 Polynomial Greatest Common Divisors
3.2* Local Analysis of the Knuth-Schonhage Algorithm
3.3 Evaluation and Interpolation
3.4* Fast Point Location in Arrangements of Hyperplanes
3.5* Vapnik-Chervonenkis Dimension and Epsilon-Nets
3.6 Exercises
3.7 Open Problems
3.8 Notes
PartⅡ.Elementary Lower Bounds
Chapter 4. Models of Computation
4.1 Straight-Line Programs and Complexity
4.2 Computation Sequences
4.3* Autarky
4.4* Computation Trees
4.5* Computation Trees and Straight-line Programs
4.6 Exercises
4.7 Notes
Chapter 5. Preconditioning and Transcendence Degree
5.1 Preconditioning
5.2 Transcendence Degree
5.3* Extension to Linearly Disjoint Fields
5.4 Exercises
5.5 Open Problems
5.6 Notes
Chapter 6. The Substitution Method
6.1 Discussion of Ideas
6.2 Lower Bounds by the Degree of Linearization
6.3* Continued Fractions, Quotients, and Composition
6.4 Exercises
6.5 Open Problems
6.6 Notes
Chapter 7. Differential Methods
7.1 Complexity of Truncated Taylor Series
7.2 Complexity of Partial Derivatives
7.3 Exercises
7.4 Open Problems
7.5 Notes
Part Ⅲ.High Degree
Chapter 8. The Degree Bound
8.1 A Field Theoretic Version of the Degree Bound
8.2 Geometric Degree and a Bezout Inequality
8.3 The Degree Bound
8.4 Applications
8.5* Estimates for the Degree
8.6* The Case of a Finite Field
8.7 Exercises
8.8 Open Problems
8.9 Notes
Chapter 9. Specific Polynomials which Are Hard to Compute
9.1 A Genetic Computation
9.2 Polynomials with Algebraic Coefficients
9.3 Applications
9.4* Polynomials with Rapidly Growing Integer Coefficients
9.5* Extension to other Complexity Measures
9.6 Exercises
9.7 Open Problems
9.8 Notes
Chapter 10. Branching and Degree
10.1 Computation Trees and the Degree Bound
10.2 Complexity of the Euclidean Representation
10.3* Degree Pattern of the Euclidean Representation
10.4 Exercises
10.5 Open Problems
10.6 Notes
Chapter 11. Branching and Connectivity
11.1 Estimation of the Number of Connected Component
11.2 Lower Bounds by the Number of Connected Components
11.3 Knapsack and Applications to Computational Geometry
11.4 Exercises
11.5 Open Problems
11.6 Notes
Chapter 12. Additive Complexity
12.1 Introduction
12.2* Real Roots of Sparse Systems of Equations
12.3 A Bound on the Additive Complexity
12.4 Exercises
12.5 Open Problems
12.6 Notes
Part Ⅳ.Low Degree
Chapter 13. Linear Complexity
13.1 The Linear Computational Model
13.2 First Upper and Lower Bounds
13.3* A Graph Theoretical Approach
13.4* Lower Bounds via Graph Theoretical Methods
13.5* Generalized Fourier Transforms
13.6 Exercises
13.7 Open Problems
13.8 Notes
Chapter 14. Multiplicative and Bilinear Complexity
14.1 Multiplicative Complexity of Quadratic Maps
14.2 The Tensorial Notation
14.3 Restriction and Conciseness
14.4 Other Characterizations of Rank
14.5 Rank of the Polynomial Multiplication
14.6 The Semiring T
14.7 Exercises
14.8 Open Problems
14.9 Notes
Chapter 15. Asymptotic Complexity of Matrix Multiplication
Chapter 16. Problems Related to Matrix Multiplication
Chapter 17. Lower Bounds for the Complexity of Algebras
Chapter 18. Rank over Finite Fields and Codes
Chapter 19. Rank of 2-Slice and 3-Slice Tensors
Chapter 20. Typical Tensorial Rank
Part Ⅴ.Complete Problems
Chapter 21. P Versus NP：A Nonuniform Algebraic Analogue
Bibliography
List of Notation
Index
缺书网
扫码进群