Аннотация
$ $This paper is a (self contained) chapter in a new book, Mathematics and
Computation, whose draft is available on my homepage 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 filed. We cover the following:
$\bullet$ Number Theory: Primality testing
$\bullet$ Combinatorial Geometry: Point-line incidences
$\bullet$ Operator Theory: The Kadison-Singer problem
$\bullet$ Metric Geometry: Distortion of embeddings
$\bullet$ Group Theory: Generation and random generation
$\bullet$ Statistical Physics: Monte-Carlo Markov chains
$\bullet$ Analysis and Probability: Noise stability
$\bullet$ Lattice Theory: Short vectors
$\bullet$ Invariant Theory: Actions on matrix tuples
Пользователи данного ресурса
Пожалуйста,
войдите в систему, чтобы принять участие в дискуссии (добавить собственные рецензию, или комментарий)