Applications of TCS to classical mathematics?

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.

-
This is a bit tricky to answer. Does combinatorics fall outside classical mathematics? – arnab Aug 17 '10 at 15:04
Combinatorics is definitely classical mathematics, but I think the same comment goes for combinatorics as goes for logic. So: finite field Kakeya conjecture is a good example, whereas new combinatorial designs motivated by PRGs are more on the fence. – Joshua Grochow Aug 17 '10 at 15:05

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

-

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

-
This was motivated by a problem on extractors/mergers (see Zeev and Avi Wigderson's later paper). Further improvements (by Madhu Sudan, Shubhangi Saraf, Swastik Kopparty and Zeev Dvir) used more ideas from theoretical computer science, specifically from list decoding of codes (the method of multiplicities). – Dana Moshkovitz Oct 17 '10 at 23:29
Two remarks: The algebraic method used by Dvir is one of the methods used to solve the classical problem about distances for planar sets. terrytao.wordpress.com/2010/11/20/… and gilkalai.wordpress.com/2010/11/20/…. – Gil Kalai Nov 23 '10 at 20:27
Second, incidence methods and results from computational and discrete geometry had earlier applications to (the real) Kakeya problem. – Gil Kalai Nov 23 '10 at 20:28

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.

-

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

-

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

-
Whether or not you count computability as part of TCS, this is an example I love that I had merely forgotten to mention. It's even cooler because it can be done using Kolmogorov complexity :). – Joshua Grochow Aug 17 '10 at 15:07

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.

-
Also, it's fair to say that components of the proof for Szemeredi's theorem through the hypergraph regularity lemma (by Gowers, Tao, Rodl, Schacht and others) were influenced by the work of Alon, Fischer, Shapira and others in developing stronger versions of the graph regularity lemma for proving testability of graph properties. – arnab Aug 17 '10 at 22:13

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).

-

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.

-

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.

-
I wasn't aware that other areas of mathematics have used the idea of reductions significantly. I would really appreciate any references or pointers you can give to such works! Also, I was under the impression that probabilistic proofs came out of pure combinatorics, and not TCS? – Joshua Grochow Nov 14 '10 at 18:39
I explained what I mean by "probabilistic proof" in the edited version of my answer. Regarding reductions: Computational complexity is an area of mathematics rooted in computer science. One characteristic of this area is the usage of reductions which plays a major role on the conceptual and technical level. It is much more developed than similar techniques in other areas of mathematics. So the art of reductions within TCS can be regarded as a major application of TCS to mathematics. I think CS-type reductions have influenced mathematicians also in other areas, and more is yet to come. – Gil Kalai Nov 15 '10 at 0:22
Joshua, let me give an analogy. Suppose somebody refers to "calculus" as one of the greatest applications of physics to classical mathematics. It can also be said that calculus is mainly important to attack problem coming from physics which were not "classical mathematics" before. Still I think calculus is the major contributions of physics to mathematics. Similarly, reductions of the type used in complexity theory is a major contribution of TCS to math. It describe a major mathematical apparatus and mathematical ideas which have independent value.(Not as important as calculus, though.) – Gil Kalai Nov 21 '10 at 21:43

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 .)

-

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.

-

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).

-

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.

-