apter 1. Introduction 1.1 Exercises 1.2 Open Problems 1.3 Notes Part I. 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-Scho(..)nhage 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 If. 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 III. 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 Components 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 IV. 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 15.1 The Exponent of Matrix Multiplication 15.2 First Estimates of the Exponent 15.3 Scalar Restriction and Extension 15.4 Degeneration and Border Rank 15.5 The Asymptotic Sum Inequality 15.6 First Steps Towards the Laser Method 15.7" Tight Sets 15.8 The Laser Method 15.9* Partial Matrix Multiplication 15.10" Rapid Multiplication of Rectangular Matrices 15.11 Exercises 15.12 Open Problems 15.13 Notes Chapter 16. Problems Related to Matrix Multiplication 16.1 Exponent of Problems 16.2 Triangular Inversion 16.3 LUP-decomposition 16.4 Matrix Inversion and Determinant 16.5" Transformation to Echelon Form 16.6" The Characteristic Polynomial 16.7" Computing a Basis for the Kernel 16.8" Orthogonal Basis Transform 16.9" Matrix Multiplication and Graph Theory 16.10 Exercises 16.11 Open Problems 16.12 Notes Chapter 17. Lower Bounds for the Complexity of Algebras 17.1 First Steps Towards Lower Bounds 17.2 Multiplicative Complexity of Associative Algebras 17.3" Multiplicative Complexity of Division Algebras 17.4" Commutative Algebras of Minimal Rank 17.5 Exercises 17.6 Open Problems 17.7 Notes Chapter 18. Rank over Finite Fields and Codes 18.1 Linear Block Codes 18.2 Linear Codes and Rank 18.3 Polynomial Multiplication over Finite Fields 18.4* Matrix Multiplication over Finite Fields 18.5* Rank of Finite Fields 18.6 Exercises 18.7 Open Problems 18.8 Notes Chapter 19. Rank of 2-Slice and 3-Slice Tensors 19.1 The Weierstraβ-Kronecker Theory 19.2 Rank of 2-Slice Tensors 19.3" Rank of 3-Slice Tensors 19.4 Exercises 19.5 Notes Chapter 20. Typical Tensorial Rank 20.1 Geometric Description 20.2 Upper Bounds on the Typical Rank 20.3* Dimension of Configurations in Formats 20.4 Exercises 20.5 Open Problems 20.6* Appendix：Topological Degeneration 20.7 Notes Part V. Complete Problems Chapter 21. P Versus NP：A Nonuniform Algebraic Analogue 21.1 Cook's Versus Valiant's Hypothesis 21.2 p-Definability and Expression Size 21.3 Universality of the Determinant 21.4 Completeness of the Permanent 21.5" The Extended Valiant Hypothesis 21.6 Exercises 21.7 Open Problems 21.8 Notes Bibliography List of Notation Index
京公网安备 11010102004214号