代数复杂性理论PDF电子书下载

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