Interactions of computational complexity theory and mathematics

Abstract

[This paper is a (modified, self contained) chapter in my recent book on computational complexity theory (Princeton University Press, 2019), called Mathematics and Computation, available online at 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 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:

• Number Theory: Primality testing
• Combinatorial Geometry: Point-line incidences
• Operator Theory: The Kadison–Singer problem
• Metric Geometry: Distortion of embeddings
• Group Theory: Generation and random generation
• Statistical Physics: Monte Carlo Markov chains
• Analysis and Probability: Noise stability
• Lattice Theory: Short vectors
• Invariant Theory: Group actions on matrix tuples (and beyond)