Ebook: Algebraic Complexity Theory: With the Collaboration of Thomas Lickteig

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 general formalization of the notions of computability and algorithm. In the 1930s, a number of quite different concepts for this purpose were pro­ posed, such as Turing machines, WHILE-programs, recursive functions, Markov algorithms, and Thue systems. All these concepts turned out to be equivalent, a fact summarized in Church's thesis, which says that the resulting definitions form an adequate formalization of the intuitive notion of computability. This had and continues to have an enormous effect. First of all, with these notions it has been possible to prove that various problems are algorithmically unsolvable. Among of group these undecidable problems are the halting problem, the word problem theory, the Post correspondence problem, and Hilbert's tenth problem. Secondly, concepts like Turing machines and WHILE-programs had a strong influence on the development of the first computers and programming languages. In the era of digital computers, the question of finding efficient solutions to algorithmically solvable problems has become increasingly important. In addition, the fact that some problems can be solved very efficiently, while others seem to defy all attempts to find an efficient solution, has called for a deeper under­ standing of the intrinsic computational difficulty of problems.

---

This is the first book to present an up-to-date and self-contained account of Algebraic Complexity Theory that is both comprehensive and unified. Requiring of the reader only some basic algebra and offering over 350 exercises, it is well-suited as a textbook for beginners at graduate level. With its extensive bibliography covering about 500 research papers, this text is also an ideal reference book for the professional researcher. The subdivision of the contents into 21 more or less independent chapters enables readers to familiarize themselves quickly with a specific topic, and facilitates the use of this book as a basis for complementary courses in other areas such as computer algebra.

---

This is the first book to present an up-to-date and self-contained account of Algebraic Complexity Theory that is both comprehensive and unified. Requiring of the reader only some basic algebra and offering over 350 exercises, it is well-suited as a textbook for beginners at graduate level. With its extensive bibliography covering about 500 research papers, this text is also an ideal reference book for the professional researcher. The subdivision of the contents into 21 more or less independent chapters enables readers to familiarize themselves quickly with a specific topic, and facilitates the use of this book as a basis for complementary courses in other areas such as computer algebra.
Content:
Front Matter....Pages I-XXIII
Introduction....Pages 1-24
Front Matter....Pages 25-25
Efficient Polynomial Arithmetic....Pages 27-59
Efficient Algorithms with Branching....Pages 61-100
Front Matter....Pages 101-101
Models of Computation....Pages 103-124
Preconditioning and Transcendence Degree....Pages 125-142
The Substitution Method....Pages 143-160
Differential Methods....Pages 161-168
Front Matter....Pages 169-169
The Degree Bound....Pages 171-206
Specific Polynomials which Are Hard to Compute....Pages 207-244
Branching and Degree....Pages 245-264
Branching and Connectivity....Pages 265-286
Additive Complexity....Pages 287-301
Front Matter....Pages 303-303
Linear Complexity....Pages 305-349
Multiplicative and Bilinear Complexity....Pages 351-374
Asymptotic Complexity of Matrix Multiplication....Pages 375-423
Problems Related to Matrix Multiplication....Pages 425-453
Lower Bounds for the Complexity of Algebras....Pages 455-488
Rank over Finite Fields and Codes....Pages 489-504
Rank of 2-Slice and 3-Slice Tensors....Pages 505-520
Typical Tensorial Rank....Pages 521-540
Back Matter....Pages 577-621
P Versus NP: A Nonuniform Algebraic Analogue....Pages 543-576

---

This is the first book to present an up-to-date and self-contained account of Algebraic Complexity Theory that is both comprehensive and unified. Requiring of the reader only some basic algebra and offering over 350 exercises, it is well-suited as a textbook for beginners at graduate level. With its extensive bibliography covering about 500 research papers, this text is also an ideal reference book for the professional researcher. The subdivision of the contents into 21 more or less independent chapters enables readers to familiarize themselves quickly with a specific topic, and facilitates the use of this book as a basis for complementary courses in other areas such as computer algebra.
Content:
Front Matter....Pages I-XXIII
Introduction....Pages 1-24
Front Matter....Pages 25-25
Efficient Polynomial Arithmetic....Pages 27-59
Efficient Algorithms with Branching....Pages 61-100
Front Matter....Pages 101-101
Models of Computation....Pages 103-124
Preconditioning and Transcendence Degree....Pages 125-142
The Substitution Method....Pages 143-160
Differential Methods....Pages 161-168
Front Matter....Pages 169-169
The Degree Bound....Pages 171-206
Specific Polynomials which Are Hard to Compute....Pages 207-244
Branching and Degree....Pages 245-264
Branching and Connectivity....Pages 265-286
Additive Complexity....Pages 287-301
Front Matter....Pages 303-303
Linear Complexity....Pages 305-349
Multiplicative and Bilinear Complexity....Pages 351-374
Asymptotic Complexity of Matrix Multiplication....Pages 375-423
Problems Related to Matrix Multiplication....Pages 425-453
Lower Bounds for the Complexity of Algebras....Pages 455-488
Rank over Finite Fields and Codes....Pages 489-504
Rank of 2-Slice and 3-Slice Tensors....Pages 505-520
Typical Tensorial Rank....Pages 521-540
Back Matter....Pages 577-621
P Versus NP: A Nonuniform Algebraic Analogue....Pages 543-576
....