Interactions of computational complexity theory and mathematics (Q6198725)

Summary: This paper is a (modified, self contained) chapter in my recent book on computational complexity theory [\textit{A. Wigderson}, Mathematics and computation. A theory revolutionizing technology and science. Princeton, NJ: Princeton University Press (2019; Zbl 1455.68004)], available online at \url{https://www.math.ias.edu/avi/book}. We survey some concrete interaction areas between computational complexity theory and different fields of mathematics. We hope to demonstrate here that hardly any area of modern mathematics is untouched by the computational connection (which in some cases is completely natural and in others may seem quite surprising). In my view, the breadth, depth, beauty, and novelty of these connections is inspiring, and speaks to a great potential of future interactions (which indeed, are quickly expanding). We aim for \textit{variety}. We give short, simple descriptions (without proofs or much technical detail) of ideas, motivations, results, and connections; this will hopefully entice the reader to dig deeper. Each vignette focuses only on a single topic within a large mathematical field, and is meant to be illustrative rather that comprehensive. We cover the following: \begin{itemize} \item Number Theory: \textit{Primality testing} \item Combinatorial Geometry: \textit{Point-line incidences} \item Operator Theory: \textit{The Kadison-Singer problem} \item Metric Geometry: \textit{Distortion of embeddings} \item Group Theory: \textit{Generation and random generation} \item Statistical Physics: \textit{Monte Carlo Markov chains} \item Analysis and Probability: \textit{Noise stability} \item Lattice Theory: \textit{Short vectors} \item Invariant Theory: \textit{Group actions on matrix tuples (and beyond)} \end{itemize} For the entire collection see [Zbl 07816356].