Mathematics and Computation: A Theory Revolutionizing Technology and Science

Avi Wigderson

Publisher:

Princeton University Press

Publication Date:

2019

Number of Pages:

440

Format:

Hardcover

Price:

49.95

ISBN:

9780691189130

Category:

Monograph

MAA Review
Table of Contents

[Reviewed by

Brian Borchers

, on

07/25/2021

]

Mathematics and Computation is a broad overview of the computer science field known as the Theory of Computation or computational complexity and the connections between ToC and mathematics.

After a couple of introductory chapters on \(\mathcal{P} \), \( \mathcal{NP} \) and other computational complexity basics, the remainder of the book consists of largely independent chapters that introduce more advanced topics in computational complexity. These include randomized algorithms, quantum computing, interactive proof systems, probabilistically checkable proofs, arithmetic complexity, space complexity, communications complexity, and cryptography.

Computational complexity theory has made use of mathematical results from areas as diverse as combinatorics, probability theory, algebra, and topology. In the reverse direction, results from computational complexity theory have also found use in many areas of mathematics. Chapter 13 includes examples of the application of computational complexity theory to problems in number theory, combinatorial geometry, metric geometry, group theory, analysis, and probability. An important recent example that appeared after the book was published was the resolution of the Connes embedding conjecture.

The style of the presentation is unusual in that the author provides formal definitions and statements of theorems but very few proofs. Examples are somewhat limited and there are no exercises. The author is very good about providing references to the primary research literature in which the proofs are given. However, there are few references to secondary or tertiary sources such as survey papers and textbooks.

For readers who are looking for a reference that they can easily dip into for particular topics, this is probably not the best starting point. Although the chapters are relatively independent of each other, the lack of proofs and relatively few examples quickly force the reader to refer to other sources. Furthermore, the lack of an index can make it hard to find a particular topic. Similarly, for mathematicians who are interested in examples of the impact of computational complexity theory on other areas of mathematics, the references mentioned in Chapter 13 may be of some interest, but the discussion of these examples in the book is not self-contained.

However, this book is recommended for readers who are interested in an overview of computational complexity theory and willing to invest the time and effort to read many of the original papers cited in the book. For example, this book could be a useful resource for a seminar for graduate students embarking on the study of computational complexity.

Brian Borchers is a professor of mathematics at New Mexico Tech and the editor of MAA Reviews.

See the publisher's website.

Tags:

Computer Science