Applications of TCS to classical mathematics?

Question

We in TCS often use powerful results and ideas from classical mathematics (algebra, topology, analysis, geometry, etc.).

What are some examples of when it has gone the other way around?

Here are some I know of (and also to give a flavor of the type of results I'm asking about):

• Cubical foams (Guy Kindler, Ryan O'Donnell, Anup Rao, and Avi Wigderson: Spherical Cubes and Rounding in High Dimensions, FOCS 2008)
• Mulmuley and Sohoni's geometric complexity theory. (Although this is technically an application of algebraic geometry and representation theory to TCS, they were led to introduce new quantum groups and new purely algebro-geometric and representation-theoretic ideas in their pursuit of P vs NP.)
• Work on metric embeddings inspired by approximation algorithms and inapproximability results

I am in particular not looking for applications of TCS to logic (finite model theory, proof theory, etc.) unless they are particularly surprising -- the relationship between TCS and logic is too close and standard and historical for the purposes of this question.

Answer 1

Expanders were developed to a large extent in TCS and they have profound connections and applications to mathematics.

Answer 2

There is Dvir's proof of the finite field Kakeya conjecture.

Answer 3

A cute example I know is Michael Freedman's paper titled "Complexity Classes as Mathematical Axioms" which gives an implication of $P^{\sharp P}\neq NP$ in the field of 3-manifold topology.

Answer 4

Invariance principles were motivated from hardness of approximation, but are useful analytic theorems. The principle: A low degree function, in which each of the variables has small influence, behaves almost the same, no matter if the inputs are independent random variables, or (corresponding) Gaussian random variables. This is a generalization of the central limit theorem; there the function is the average of the variables.

Noise stability of functions with low influences: invariance and optimality E. Mossel, R. O'Donnell, K. Oleszkiewicz. Annals of Mathematics 171(1), pp. 295-341 (2010). FOCS '05.

Low degree testing theorems were motivated by PCP applications, but are interesting algebraic theorems. The principle: An $n$-variate function over a finite field $F$ that, on average over the lines in $F^n$, is close in Hamming distance to a low degree polynomial on the line, is close in Hamming distance to a low degree polynomial on the entire $F^n$.

Closeness in Hamming distance to a low degree polynomial in a certain space means that the function identifies with a low degree polynomial on some non-negligible fraction of the space.

Improved Low-Degree Testing and its Applications. S. Arora and M. Sudan. In ACM STOC 1997.

A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP, R.Raz, S.Safra, Proceeding of the 29th STOC, 1997, pp. 475-484

Answer 5

Is computability theory part of TCS? If so, then Computability Theory and Differential Geometry by Bob Soare, which exposits applications of results he obtained with Csima, is an example.

Don't know why the link isn't showing up.... Here: http://www.people.cs.uchicago.edu/~soare/res/Geometry/geom.pdf

Answer 6

Although I am biased, I think it's fair to say that various ideas from TCS have contributed to progress on the inverse conjecture for the Gowers norm, see e.g. the paper by Green and Tao.

Answer 7

Extractors is another place to look. For example, the paper by Barak-Kindler-Shaltiel-Sudakov-Wigerson'04 gives (among other things) improved constructions of Ramsey graphs (a problem that had been open for a while in discrete maths).

Answer 8

De Wolf and Drucker mention in their survey on quantum proofs about surprising connection between quantum query complexity and $\epsilon$-approximation of symmetric functions by polynomials.

Answer 9

Let me mention a couple more applications:

Perhaps the most important contribution of TCS to pure mathematics is the art of reductions. Reductions of the form used by TCS in computational complexity and other places represent a mathematical paradigm/tool which is more developed in TCS compared to other areas of math.

The notion of a probabilistic proof: Here I do not refer to the probabilistic method (which is rooted in mathematics but have many applications to CS) but rather to the fact that a mathematical statement like the statement claiming a certain number is a prime, can be given a proof "beyond any reasonable doubt". It is a conceptual breakthrough comming from CS, although it did not have yet much applications in the way mathematics is practiced.

Answer 10

The Zig-Zag expander construction was used for constructing various interesting examples of groups with certain unexpected properties, see Meshulam-Wigderson , Rozenman-Shalev-Wigderson. The construction itself is very interesting from a pure math viewpoint, since it used completely different tools (motivated by the CS viewpoint of dealing with entropy) to build expanders than previous constructions. (However perhaps the most celebrated application is inside TCS- Reingold's logspace algorithm for undirected connectivity .)

Answer 11

Moser's constructive proof of the Lovasz Local Lemma uses computer science ideas, gives a new proof of Lovasz Local lemma, and solves a problem that people have been thinking about for quite some time.

Answer 12

One example that comes to mind is Higman's Embedding Theorem and it's group theoretic consequences.

Higman's Embedding Theorem: A group G is finitely generated with a recursive presentation iff G is a subgroup of a finitely presented group.

(Notice that the left part of the equivalence has a computational component while the right is purely group theoretic).

Answer 13

The meaning of randomness, what accounts as a "random sequence" and related questions were important in mathematics, probability theory, and statistics for centuries. Theoretical computer science (and complexity theory) offers very robust deep and convincing insights for the understanding of randomness.

While the probabilistic method started in mathematics derandomization which is an important mathematical concept is mainly developed in CS.

This is related to Moritz's answer.