Chapter 1. Introduction 1
1.1 Exercises 20
1.2 Open Problems 23
1.3 Notes 23
Part Ⅰ. Fundamental Algorithms 27
Chapter 2. Efficient Polynomial Arithmetic 27
2.1 Multiplication of Polynomials Ⅰ 28
2.2 Multiplication of Polynomials Ⅱ 34
2.3 Multiplication of Several Polynomials 38
2.4 Multiplication and Inversion of Power Series 44
2.5 Composition of Power Series 47
2.6 Exercises 53
2.7 Open Problems 57
2.8 Notes 58
Chapter 3. Efficient Algorithms with Branching 61
3.1 Polynomial Greatest Common Divisors 61
3.2 Local Analysis of the Knuth-Schonhage Algorithm 71
3.3 Evaluation and Interpolation 75
3.4 Fast Point Location in Arrangements of Hyperplanes 79
3.5 Vapnik-Chervonenkis Dimension and Epsilon-Nets 84
3.6 Exercises 90
3.7 Open Problems 97
3.8 Notes 98
Part Ⅱ. Elementary Lower Bounds 103
Chapter 4. Models of Computation 103
4.1 Straight-Line Programs and Complexity 103
4.2 Computation Sequences 109
4.3 Autarky 111
4.4 Computation Trees 113
4.5 Computation Trees and Straight-line Programs 118
4.6 Exercises 121
4.7 Notes 124
Chapter 5. Preconditioning and Transcendence Degree 125
5.1 Preconditioning 125
5.2 Transcendence Degree 130
5.3 Extension to Linearly Disjoint Fields 134
5.4 Exercises 136
5.5 Open Problems 142
5.6 Notes 142
Chapter 6. The Substitution Method 143
6.1 Discussion of Ideas 144
6.2 Lower Bounds by the Degree of Linearization 148
6.3 Continued Fractions，Quotients，and Composition 151
6.4 Exercises 157
6.5 Open Problems 159
6.6 Notes 159
Chapter 7. Differential Methods 161
7.1 Complexity of Truncated Taylor Series 161
7.2 Complexity of Partial Derivatives 164
7.3 Exercises 167
7.4 Open Problems 168
7.5 Notes 168
Part Ⅲ. High Degree 171
Chapter 8. The Degree Bound 171
8.1 A Field Theoretic Version of the Degree Bound 171
8.2 Geometric Degree and a Bezout Inequality 178
8.3 The Degree Bound 182
8.4 Applications 186
8.5 Estimates for the Degree 192
8.6 The Case of a Finite Field 195
8.7 Exercises 198
8.8 Open Problems 205
8.9 Notes 205
Chapter 9.Specific Polynomials which Are Hard to Compute 207
9.1 A Generic Computation 207
9.2 Polynomials with Algebraic Coefficients 211
9.3 Applications 218
9.4 Polynomials with Rapidly Growing Integer Coefficients 224
9.5 Extension to other Complexity Measures 230
9.6 Exercises 236
9.7 Open Problems 243
9.8 Notes 243
Chapter 10. Branching and Degree 245
10.1 Computation Trees and the Degree Bound 245
10.2 Complexity of the Euclidean Representation 248
10.3 Degree Pattern of the Euclidean Representation 253
10.4 Exercises 260
10.5 Open Problems 263
10.6 Notes 264
Chapter 11. Branching and Connectivity 265
11.1 Estimation of the Number of Connected Components 265
11.2 Lower Bounds by the Number of Connected Components 272
11.3 Knapsack and Applications to Computational Geometry 275
11.4 Exercises 278
11.5 Open Problems 282
11.6 Notes 283
Chapter 12. Additive Complexity 287
12.1 Introduction 287
12.2 Real Roots of Sparse Systems of Equations 289
12.3 A Bound on the Additive Complexity 296
12.4 Exercises 298
12.5 Open Problems 300
12.6 Notes 301
Part Ⅳ. Low Degree 305
Chapter 13. Linear Complexity 305
13.1 The Linear Computational Model 305
13.2 First Upper and Lower Bounds 309
13.3 A Graph Theoretical Approach 314
13.4 Lower Bounds via Graph Theoretical Methods 318
13.5 Generalized Fourier Transforms 326
13.6 Exercises 345
13.7 Open Problems 348
13.8 Notes 348
Chapter 14. Multiplicative and Bilinear Complexity 351
14.1 Multiplicative Complexity of Quadratic Maps 351
14.2 The Tensorial Notation 357
14.3 Restriction and Conciseness 361
14.4 Other Characterizations of Rank 365
14.5 Rank of the Polynomial Multiplication 367
14.6 The Semiring T 368
14.7 Exercises 370
14.8 Open Problems 373
14.9 Notes 373
Chapter 15. Asymptotic Complexity of Matrix Multiplication 375
15.1 The Exponent of Matrix Multiplication 375
15.2 First Estimates of the Exponent 377
15.3 Scalar Restriction and Extension 381
15.4 Degeneration and Border Rank 384
15.5 The Asymptotic Sum Inequality 389
15.6 First Steps Towards the Laser Method 391
15.7 Tight Sets 396
15.8 The Laser Method 401
15.9 Partial Matrix Multiplication 407
15.10 Rapid Multiplication of Rectangular Matrices 411
15.11 Exercises 412
15.12 Open Problems 419
15.13 Notes 420
Chapter 16. Problems Related to Matrix Multiplication 425
16.1 Exponent of Problems 425
16.2 Triangular Inversion 427
16.3 L UP-decomposition 428
16.4 Matrix Inversion and Determinant 430
16.5 Transformation to Echelon Form 431
16.6 The Characteristic Polynomial 435
16.7 Computing a Basis for the Kernel 439
16.8 Orthogonal Basis Transform 441
16.9 Matrix Multiplication and Graph Theory 445
16.10 Exercises 447
16.11 Open Problems 451
16.12 Notes 452
Chapter 17. Lower Bounds for the Complexity of Algebras 455
17.1 First Steps Towards Lower Bounds 455
17.2 Multiplicative Complexity of Associative Algebras 463
17.3 Multiplicative Complexity of Division Algebras 470
17.4 Commutative Algebras of Minimal Rank 474
17.5 Exercises 481
17.6 Open Problems 484
17.7 Notes 485
Chapter 18. Rank over Finite Fields and Codes 489
18.1 Linear Block Codes 489
18.2 Linear Codes and Rank 491
18.3 Polynomial Multiplication over Finite Fields 492
18.4 Matrix Multiplication over Finite Fields 494
18.5 Rank of Finite Fields 496
18.6 Exercises 498
18.7 Open Problems 502
18.8 Notes 502
Chapter 19. Rank of 2-Slice and 3-Slice Tensors 505
19.1 The WeierstraB-Kronecker Theory 505
19.2 Rank of 2-Slice Tensors 508
19.3 Rank of 3-Slice Tensors 512
19.4 Exercises 516
19.5 Notes 519
Chapter 20. Typical Tensorial Rank 521
20.1 Geometric Description 521
20.2 Upper Bounds on the Typical Rank 524
20.3 Dimension of Configurations in Formats 531
20.4 Exercises 534
20.5 Open Problems 536
20.6 Appendix：Topological Degeneration 536
20.7 Notes 539
Part Ⅴ. Complete Problems 543
Chapter 21. P Versus NP：A Nonuniform Algebraic Analogue 543
21.1 Cook’s Versus Valiant’s Hypothesis 543
21.2 p-Definability and Expression Size 550
21.3 Universality of the Determinant 554
21.4 Completeness of the Permanent 556
21.5 The Extended Valiant Hypothesis 561
21.6 Exercises 569
21.7 Open Problems 574
21.8 Notes 574
Bibliography 577
List of Notation 601
Index 609