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

Answer 1

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

Answer 2

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 3

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

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-Wigderson'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

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 10

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

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

Answer 13

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!

References.

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

Answer 14

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 15

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.

Answer 16

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

Answer 17

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.