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)
  • The Geometric Complexity Theory Program. (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.

  • 1
    This is a bit tricky to answer. Does combinatorics fall outside classical mathematics? – arnab Aug 17 '10 at 15:04
  • 2
    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
  • You can find good examples by looking for results published in, say, Annals of Math by the TCS community. – MCH Oct 24 '13 at 6:42

17 Answers 17

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.

  • 3
    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
  • 1
    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
  • 2
    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

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.

  • 7
    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

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

  • 2
    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

Extractors is another place to look. For example, the paper by Barak-Kindler-Shaltiel-Sudakov-Wigderson'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.

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

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.

  • 1
    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
  • 3
    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
  • @JoshuaGrochow Many proofs begin with something like, "We may assume that $G$ is connected, since the number of widgets in a graph is the sum/product of the number of widgets in each component", and often more sophisticated versions of this kind of idea. Does that count as a reduction from the general problem to the connected problem? On the other hand, mathematicians were probably doing that long before computational complexity theory came along. – David Richerby Sep 4 '13 at 9:48
  • 1
    @JoshuaGrochow it will not be hard to find non-trivial examples of "general case to special reductions". For example, the Cassaza survey I linked in my answer has tons of non-trivial reductions between problems equivalent to the Kadison-Singer problem, some of them very restricted on first glance. It's my understanding that arithmetic geometry is full of such things as well, you might know more. I am not sure to what extent TCS can claim credit for introducing this approach to intractable problems. – Sasho Nikolov Oct 23 '13 at 21:35

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.

The Batson-Spielman-Srivastava barrier function method has had a number of applications to geometry and functional analysis, arose in computer science, and is a very original form of potential function argument, reminiscent of the method of pessimistic estimators. Moreover, it goes against the conventional wisdom that analyzing the characteristic polynomial of random matrices is intractable, and one is better off looking at matrix moments instead.

The barrier function method was first developed to prove the existence of (and construct in deterministic polynomial time) sparsifiers of graphs that preserve their spectral properties. Such sparsifiers were motivated by algorithmic applications: essentially any algorithm that needs to compute cuts approximately can be sped up by being given as input a sparsified version of the original input.

Beyond sparsifiers however, the method has had numerous applications, many of which are surveyed by Assaf Naor in this paper. Some prominent examples are construction of weighted expander graphs, approximate John decompositions of the identity with fewer points, dimension reduction of subsets/subspaces of $\ell_1^n$, a tight version of Bourgain and Tzafriri's restricted invertibility principle. For all of the above applications, the barrier function method yields essentially tight bounds, gives an efficient deterministic algorithm in addition to an existence proof, and often provides a more elementary proof than prior methods (although not without some hairy calculations).

Fast forward to 2013, and the barrier function method, on steroids, and augmented with the machinery of interlacing polynomials, was used by Marcus, Srivastava, and Spielman, to solve one of the most notorious problems in functional analysis, the Kadison-Singer problem. This problem arises from fundamental questions in mathematical physics, but it goes much further - it is known to be equivalent to dozens of problems all over mathematics. Not to mention that many analysts (including Kadison and Singer) did not even think the problem had a positive resolution (the cited survey by Cassaza et al. speculates on possible counterexamples).

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

  • 1
    This connection has also been extended to complexity: the nondeterministic time complexity of the word problem in any group $G$ is polynomially related to the smallest isoperimetric (Dehn) function of any finitely presented group $H$ in which $G$ can be embedded. In particular, $Word(G) \in NP$ iff $G$ can be embedded in a finitely presented group with at most polynomial isoperimetric function. Birget, Ol'shanksii, Rips, and Sapir, Annals of Math. 2002 ams.org/mathscinet-getitem?mr=1933724 – Joshua Grochow Oct 23 '13 at 15:57

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.

Automata theory and algebraicity

Automata theory has given some interesting results to characterize algebraicity. I mention two of them, with references. It is by no way exhaustive.

1. An algebraic closure of $\mathbb F_q(t)$

Let $\mathbb F_q(t)$ be the rational function field over the finite field with $q$ elements, where $q=p^s$ for some prime $p$ and integer $s$. Let $\mathbb F_q[[t]]$ be the ring of formal power series over $\mathbb F_q$.

One can characterize the power series which are algebraic over $\mathbb F_q(t)$, that is roots of a monic polynomial with coefficients in $\mathbb F_q(t)$, using an automata-theoretic description.

Theorem (Christol [1]). A formal power series $\sum_{i=0}^{\infty} a_i t^i$ is algebraic over $\mathbb F_q(t)$ if and only if the sequence $\{a_i\}_{i=0}^\infty$ is $p$-automatic.

Actually, this method allows to give a description of an algebraic closure of $\mathbb F_q(t)$. It is known that the field of generalized power series of the form $$\sum_{i\in I} x_i t^i\text,$$ where $I$ is a well-ordered subset of $\mathbb Q$, contains an algebraic closure of $\mathbb F_q(t)$. Again, the generalized power series which are algebraic can be characterized using an automata-theoretic description.

Theorem (Kedlaya [2]). A generalized power series $\sum_{i\in I} a_i t^i$ is algebraic over $\mathbb F_q(t)$ if and only if the sequence $\{a_i\}_{i\in I}$ is $p$-quasi-automatic.

2. Transcendental numbers

Automatic sequences are also used to characterize transcendental numbers. For instance,

Theorem (Adamczewski & Bugeaud [3]). Let $b$ be an integer $\ge 2$. Let $x\in\mathbb R$ and let $\mathbf x=\{x_i\}_{i=0}^\infty$ be the sequence of digits of its base-$b$ representation.

  1. If $\mathbf x$ is ultimately periodic, then $x$ is rational;
  2. If $\mathbf x$ is $b$-automatic (but not ultimately periodic), then $x$ is transcendental;
  3. Else, $x$ is an algebraic irrational number.

Of course, the first item is a very classic result!


[1] Gilles Christol. Ensembles presque périodiques k-reconnaissables. In Theoretical Computer Science 9(1), pp 141-145, 1979.

[2] Kiran S. Kedlaya. Finite automata and algebraic extensions of function fields. In Journal de théorie des nombres de Bordeaux 18, pp 379-420, 2006. arXiv:math/0410375.

[3] Boris Adamcweski, Yann Bugeaud. On the complexity of algebraic numbers I. Expansions in integer bases. In Annals of Mathematics 165(2), pp 547-565, 2007.

  • theorem (Adamczewski & Bugeaud [3]) may be wrong or be misunderstood – XL _at_China Jan 6 at 0:13

In his paper Straight Line Programs and Torsion Points on Elliptic Curves, Qi Cheng relates Bürgisser's $L$-conjecture (a variant of Shub and Smale's $\tau$-conjecture¹) to the Torsion Theorem and to Masser's Theorem in the field of elliptic curves.

Very roughly, if the $L$-conjecture is true (or a weaker version of it), then one can "easily" deduce these both theorems. Their original proofs are much harder.

¹ The $\tau$-conjecture asserts that if a polynomial $p$ has a constant-free straight-line program (or arithmetic circuit) of size $\tau$, its number of integer roots is at most $(1+\tau)^c$ for some absolute constant $c$.

IMHO TCS is a branch of mathematics and I would put it a bit broader. We live in the algorithmic age, almost everybody, in all human activities, invents/reinvents algorithms, mainly heuristics. But some of those algorithms are 1. good; 2. contain (burried) answers to deep mathematical questions; 3. Wait for a professional mathematical analysis/improvement/attention. My personal experience: a stunning power of one physics/machine learning heuristic, namely the Bethe Approximation, as a proof technique. The main problem is that possible encounters of this kind mainly happen in the industry, where nobody cares about those non-product related insights/revelations.

protected by Kaveh Oct 23 '13 at 19:36

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.