<p><strong>Expanders</strong> were developed to a large extent in TCS and they have profound connections and applications to mathematics. </p>

CC BY-SA 2.5
2010-10-28T05:39:49.290Z
2010-11-15T02:02:35.573Z
2010-11-15T02:02:35.573Z
Gil Kalai
<p>A cute example I know is Michael Freedman's paper titled "<a href="http://arxiv.org/abs/0810.0033">Complexity Classes as Mathematical Axioms</a>" which gives an implication of $P^{\sharp P}\neq NP$ in the field of 3-manifold topology.</p>

CC BY-SA 2.5
2010-08-17T16:19:51.593Z
2010-08-19T21:58:24.660Z
2010-08-19T21:58:24.660Z
Zeyu
<p>There is Dvir's <a href="http://www.math.ias.edu/~dvir/papers/Dvir09.pdf">proof</a> of the finite field Kakeya conjecture.</p>

CC BY-SA 2.5
2010-10-17T23:29:40.893Z
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
CC BY-SA 2.5
2010-11-23T20:27:48.843Z
Two remarks: The algebraic method used by Dvir is one of the methods used to solve the classical problem about distances for planar sets. http://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/ and http://gilkalai.wordpress.com/2010/11/20/janos-pach-guth-and-katzs-solution-of-erdos-distinct-distances-problem/.
Gil Kalai
CC BY-SA 2.5
2010-11-23T20:28:54.397Z
Second, incidence methods and results from computational and discrete geometry had earlier applications to (the real) Kakeya problem.
Gil Kalai
CC BY-SA 2.5
2010-08-17T14:56:55.143Z
2010-10-18T16:43:18.120Z
2010-10-18T16:43:18.120Z
Aaron Roth
<p><strong>Invariance principles</strong> 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.</p>

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

<p><strong>Low degree testing theorems</strong> 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 <em>on the line</em>, is close in Hamming distance to a low degree polynomial on the entire $F^n$.</p>

<p>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.</p>

<p><em>Improved Low-Degree Testing and its Applications</em>.
S. Arora and M. Sudan. In ACM STOC 1997.</p>

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

CC BY-SA 2.5
2010-10-17T23:22:05.523Z
2010-10-17T23:22:05.523Z
Dana Moshkovitz
<p>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 <a href="http://arxiv.org/abs/0711.3191">paper by Green and Tao</a>.</p>

CC BY-SA 2.5
2010-08-17T22:13:21.270Z
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
CC BY-SA 2.5
2010-08-17T21:37:24.423Z
2010-08-17T21:37:24.423Z
Manu
<p>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.</p>

<p>Don't know why the link isn't showing up....  Here: <a href="http://www.people.cs.uchicago.edu/~soare/res/Geometry/geom.pdf">http://www.people.cs.uchicago.edu/~soare/res/Geometry/geom.pdf</a></p>

CC BY-SA 2.5
2010-08-17T15:07:22.060Z
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
CC BY-SA 2.5
2010-08-17T15:03:19.327Z
2010-08-17T15:03:19.327Z
Aaron Sterling
<p>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).</p>

CC BY-SA 3.0
2010-08-17T15:05:01.583Z
2015-04-12T21:47:56.737Z
2015-04-12T21:47:56.737Z
Moritz
<p>The <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SALIL/EXPANDERS/ANNALS/RVW01.pdf">Zig-Zag expander construction</a> was used for constructing various interesting examples of groups with certain unexpected properties, see <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/MW01/Final.pdf">Meshulam-Wigderson</a> , <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/RSW05/rsw05.pdf">Rozenman-Shalev-Wigderson</a>. 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- <a href="http://www.wisdom.weizmann.ac.il/~reingold/publications/sl.ps">Reingold's logspace algorithm for undirected connectivity</a> .)</p>

CC BY-SA 2.5
2010-10-29T04:45:15.467Z
2010-10-29T04:45:15.467Z
Boaz Barak
<p>De Wolf and Drucker mention in <a href="http://arxiv.org/abs/0910.3376">their survey on quantum proofs</a> about surprising connection between quantum query complexity and $\epsilon$-approximation of symmetric functions by polynomials.</p>

CC BY-SA 2.5
2010-08-17T16:22:24.133Z
2010-08-17T23:33:55.127Z
2010-08-17T23:33:55.127Z
ilyaraz
<p>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.</p>

CC BY-SA 2.5
2010-11-16T02:43:38.770Z
2010-11-16T02:43:38.770Z
Peter Shor 
<p>Let me mention a couple more applications: </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-15T00:22:01.800Z
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
CC BY-SA 2.5
2010-11-21T21:43:06.677Z
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
CC BY-SA 2.5
2010-11-14T18:39:58.777Z
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
CC BY-SA 3.0
2013-09-04T09:48:47.470Z
@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
CC BY-SA 3.0
2013-09-05T02:01:05.870Z
@DavidRicherby: That of course counts as a reduction (indeed, such reductions to the connected case of a graph problem often occur in complexity as well), but a very simple kind of reduction. The more interesting reductions are usually from the general case to a much more restrictive case (e.g. from general graphs to, say, trivalent graphs) or to a seemingly unrelated type of problem (e.g. from a graph problem to a scheduling optimization problem, or a logic problem, or a number theory problem, a knot problem, etc.)
Joshua Grochow
CC BY-SA 3.0
2013-10-23T21:35:56.447Z
@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
CC BY-SA 2.5
2010-11-14T18:15:36.850Z
2010-11-15T00:11:13.897Z
2010-11-15T00:11:13.897Z
Gil Kalai
<p>The <a href="http://arxiv.org/pdf/0808.0163v3.pdf" rel="noreferrer">Batson-Spielman-Srivastava</a> 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.</p>

<p>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. </p>

<p>Beyond sparsifiers however, the method has had numerous applications, many of which are surveyed by Assaf Naor in <a href="http://arxiv.org/abs/1101.4324" rel="noreferrer">this paper</a>. 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).</p>

<p>Fast forward to 2013, and the barrier function method, on steroids, and augmented with the machinery of interlacing polynomials, was used by <a href="http://arxiv.org/abs/1306.3969" rel="noreferrer">Marcus, Srivastava, and Spielman</a>, to solve one of the most notorious problems in functional analysis, the Kadison-Singer problem. This problem arises from <a href="http://www.soulphysics.org/2013/06/philosophy-and-physics-in-the-kadison-singer-conjecture/" rel="noreferrer">fundamental questions</a> in mathematical physics, but it goes much further - it is known to be <a href="http://arxiv.org/abs/math/0510024" rel="noreferrer">equivalent</a> 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).</p>

CC BY-SA 3.0
2013-10-23T05:49:20.220Z
2013-10-23T21:28:22.327Z
2013-10-23T21:28:22.327Z
Sasho Nikolov
<p>The meaning of <strong>randomness</strong>, 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. </p>

<p>While the probabilistic method started in mathematics <strong>derandomization</strong> which is an important mathematical concept is mainly developed in CS.</p>

<p>This is related to <a href="https://cstheory.stackexchange.com/questions/149/applications-of-tcs-to-classical-mathematics/157#157">Moritz</a>'s answer.</p>

CC BY-SA 2.5
2010-11-23T20:35:15.220Z
2010-11-23T20:35:15.220Z
2017-04-13T12:32:28.080Z
Gil Kalai
<h2>Automata theory and algebraicity</h2>
<p>Automata theory has given some interesting results to characterize algebraicity. I mention two of them, with references. It is by no way exhaustive.</p>
<h3>1. An algebraic closure of <span class="math-container">$\mathbb F_q(t)$</span></h3>
<p>Let <span class="math-container">$\mathbb F_q(t)$</span> be the rational function field over the finite field with <span class="math-container">$q$</span> elements, where <span class="math-container">$q=p^s$</span> for some prime <span class="math-container">$p$</span> and integer <span class="math-container">$s$</span>. Let <span class="math-container">$\mathbb F_q[[t]]$</span> be the ring of formal power series over <span class="math-container">$\mathbb F_q$</span>.</p>
<p>One can characterize the power series which are <em>algebraic over <span class="math-container">$\mathbb F_q(t)$</span></em>, that is roots of a monic polynomial with coefficients in <span class="math-container">$\mathbb F_q(t)$</span>, using an automata-theoretic description.</p>
<p><strong>Theorem (Christol [1]).</strong> A formal power series <span class="math-container">$\sum_{i=0}^{\infty} a_i t^i$</span> is algebraic over <span class="math-container">$\mathbb F_q(t)$</span> if and only if the sequence <span class="math-container">$\{a_i\}_{i=0}^\infty$</span> is <span class="math-container">$p$</span>-automatic.</p>
<p>Actually, this method allows to give a description of an algebraic closure of <span class="math-container">$\mathbb F_q(t)$</span>. It is known that the field of <em>generalized power series</em> of the form
<span class="math-container">$$\sum_{i\in I} x_i t^i\text,$$</span>
where <span class="math-container">$I$</span> is a well-ordered subset of <span class="math-container">$\mathbb Q$</span>, contains an algebraic closure of <span class="math-container">$\mathbb F_q(t)$</span>. Again, the generalized power series which are algebraic can be characterized using an automata-theoretic description.</p>
<p><strong>Theorem (Kedlaya [2]).</strong> A generalized power series <span class="math-container">$\sum_{i\in I} a_i t^i$</span> is algebraic over <span class="math-container">$\mathbb F_q(t)$</span> if and only if the sequence <span class="math-container">$\{a_i\}_{i\in I}$</span> is <span class="math-container">$p$</span>-quasi-automatic.</p>
<h3>2. Transcendental numbers</h3>
<p>Automatic sequences are also used to characterize transcendental numbers. For instance,</p>
<p><strong>Theorem (Adamczewski &amp; Bugeaud [3]).</strong> Let <span class="math-container">$b$</span> be an integer <span class="math-container">$\ge 2$</span>. Let <span class="math-container">$x\in\mathbb R$</span> and let <span class="math-container">$\mathbf x=\{x_i\}_{i=0}^\infty$</span> be the sequence of digits of its base-<span class="math-container">$b$</span> representation.</p>
<ol>
<li>If <span class="math-container">$\mathbf x$</span> is ultimately periodic, then <span class="math-container">$x$</span> is rational;</li>
<li>If <span class="math-container">$\mathbf x$</span> is <span class="math-container">$b$</span>-automatic (but not ultimately periodic), then <span class="math-container">$x$</span> is transcendental;</li>
<li>Else, <span class="math-container">$x$</span> is an algebraic irrational number.</li>
</ol>
<p>Of course, the first item is a very classic result!</p>
<blockquote>
<p><strong>References.</strong></p>
<p>[1] Gilles Christol. <a href="http://www.sciencedirect.com/science/article/pii/0304397579900112" rel="noreferrer"><strong>Ensembles presque périodiques k-reconnaissables</strong></a>. In <em>Theoretical Computer Science</em> <strong>9</strong>(1), pp 141-145, 1979.</p>
<p>[2] Kiran S. Kedlaya. <a href="http://www.emis.de/journals/JTNB/2006-2/article07.pdf" rel="noreferrer"><strong>Finite automata and algebraic extensions of function
fields</strong></a>. In <em>Journal de théorie des nombres de Bordeaux</em> <strong>18</strong>, pp 379-420, 2006. arXiv:<a href="http://arxiv.org/abs/math/0410375" rel="noreferrer">math/0410375</a>.</p>
<p>[3] Boris Adamcweski, Yann Bugeaud. <a href="http://annals.math.princeton.edu/2007/165-2/p04" rel="noreferrer"><strong>On the complexity of algebraic numbers I. Expansions in integer bases</strong></a>. In <em>Annals of Mathematics</em> <strong>165</strong>(2), pp 547-565, 2007.</p>
</blockquote>

CC BY-SA 3.0
2018-01-06T00:13:17.037Z
theorem (Adamczewski & Bugeaud [3]) may be wrong or be misunderstood
XL _At_Here_There
CC BY-SA 3.0
2014-01-13T10:29:21.777Z
2014-01-13T10:29:21.777Z
2020-06-17T09:38:08.363Z
Bruno
<p>In his paper <a href="http://www.cs.ou.edu/~qcheng/paper/BSS.pdf" rel="noreferrer"><strong>Straight Line Programs and Torsion Points on Elliptic Curves</strong></a>, 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. </p>

<p>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.</p>

<p>¹ 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$.</p>

CC BY-SA 3.0
2014-01-11T08:22:35.960Z
2014-01-11T08:22:35.960Z
Bruno
<p>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. </p>

CC BY-SA 3.0
2013-10-23T19:08:06.063Z
2013-10-23T19:08:06.063Z
leonid gurvits
<p>We in TCS often use powerful results and ideas from classical mathematics (algebra, topology, analysis, geometry, etc.).  </p>

<blockquote>
  <p>What are some examples of when it has gone the other way around?  </p>
</blockquote>

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

<ul>
<li>Cubical foams (Guy Kindler, Ryan O'Donnell, Anup Rao, and Avi Wigderson: Spherical Cubes and Rounding in High Dimensions, FOCS 2008)</li>
<li>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.)</li>
<li>Work on metric embeddings inspired by approximation algorithms and inapproximability results</li>
</ul>

<p>I am in particular <em>not</em> 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.</p>

CC BY-SA 3.0
2013-10-24T06:42:51.157Z
You can find good examples by looking for results published in, say, Annals of Math by the TCS community.
Mahdi Cheraghchi
CC BY-SA 2.5
2010-08-17T15:04:12.227Z
This is a bit tricky to answer.  Does combinatorics fall outside classical mathematics?
arnab
CC BY-SA 2.5
2010-08-17T15:05:46.980Z
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
<reference-request><big-list>
Applications of TCS to classical mathematics?
Joshua Grochow
# Applications of TCS to classical mathematics?

(Asked by: username_0 on 2010-08-17)

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.

**Tags:** reference-request, big-list
> **Comments:**
> **username_2**: This is a bit tricky to answer.  Does combinatorics fall outside classical mathematics?  
> **username_0**: 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.  
> **username_1**: You can find good examples by looking for results published in, say, Annals of Math by the TCS community.  

---

## 16 answers

### Answer by username_3 on 2010-10-28. Score: 34

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


---

### Answer by username_4 on 2010-08-17. Score: 22

A cute example I know is Michael Freedman's paper titled "[Complexity Classes as Mathematical Axioms](http://arxiv.org/abs/0810.0033)" which gives an implication of $P^{\sharp P}\neq NP$ in the field of 3-manifold topology.


---

### Answer by username_5 on 2010-08-17. Score: 22

There is Dvir's [proof](http://www.math.ias.edu/~dvir/papers/Dvir09.pdf) of the finite field Kakeya conjecture.

> **Comments:**
> **username_6**: 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).  
> **username_3**: Two remarks: The algebraic method used by Dvir is one of the methods used to solve the classical problem about distances for planar sets. http://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/ and http://gilkalai.wordpress.com/2010/11/20/janos-pach-guth-and-katzs-solution-of-erdos-distinct-distances-problem/.  
> **username_3**: Second, incidence methods and results from computational and discrete geometry had earlier applications to (the real) Kakeya problem.  

---

### Answer by username_6 on 2010-10-17. Score: 21

**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 by username_7 on 2010-08-17. Score: 19

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](http://arxiv.org/abs/0711.3191).

> **Comments:**
> **username_2**: 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.  

---

### Answer by username_8 on 2010-08-17. Score: 19

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>

> **Comments:**
> **username_0**: 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 :).  

---

### Answer by username_9 on 2010-08-17. Score: 17

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 by username_11 on 2010-08-17. Score: 15

De Wolf and Drucker mention in [their survey on quantum proofs](http://arxiv.org/abs/0910.3376) about surprising connection between quantum query complexity and $\epsilon$-approximation of symmetric functions by polynomials.


---

### Answer by username_10 on 2010-10-29. Score: 13

The [Zig-Zag expander construction](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SALIL/EXPANDERS/ANNALS/RVW01.pdf) was used for constructing various interesting examples of groups with certain unexpected properties, see [Meshulam-Wigderson](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/MW01/Final.pdf) , [Rozenman-Shalev-Wigderson](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/RSW05/rsw05.pdf). 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](http://www.wisdom.weizmann.ac.il/~reingold/publications/sl.ps) .)


---

### Answer by username_12 on 2010-11-16. Score: 10

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 by username_3 on 2010-11-14. Score: 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.

> **Comments:**
> **username_0**: 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?  
> **username_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.  
> **username_3**: 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.)  
> **username_13**: @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.  
> **username_0**: @DavidRicherby: That of course counts as a reduction (indeed, such reductions to the connected case of a graph problem often occur in complexity as well), but a very simple kind of reduction. The more interesting reductions are usually from the general case to a much more restrictive case (e.g. from general graphs to, say, trivalent graphs) or to a seemingly unrelated type of problem (e.g. from a graph problem to a scheduling optimization problem, or a logic problem, or a number theory problem, a knot problem, etc.)  
> **username_14**: @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.  

---

### Answer by username_14 on 2013-10-23. Score: 10

The [Batson-Spielman-Srivastava](http://arxiv.org/pdf/0808.0163v3.pdf) 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](http://arxiv.org/abs/1101.4324). 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](http://arxiv.org/abs/1306.3969), to solve one of the most notorious problems in functional analysis, the Kadison-Singer problem. This problem arises from [fundamental questions](http://www.soulphysics.org/2013/06/philosophy-and-physics-in-the-kadison-singer-conjecture/) in mathematical physics, but it goes much further - it is known to be [equivalent](http://arxiv.org/abs/math/0510024) 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 by username_15 on 2014-01-13. Score: 7

## 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**](http://www.sciencedirect.com/science/article/pii/0304397579900112). In *Theoretical Computer Science* **9**(1), pp 141-145, 1979.
>
> [2] Kiran S. Kedlaya. [**Finite automata and algebraic extensions of function
> fields**](http://www.emis.de/journals/JTNB/2006-2/article07.pdf). In *Journal de théorie des nombres de Bordeaux* **18**, pp 379-420, 2006. arXiv:[math/0410375](http://arxiv.org/abs/math/0410375).
>
> [3] Boris Adamcweski, Yann Bugeaud. [**On the complexity of algebraic numbers I. Expansions in integer bases**](http://annals.math.princeton.edu/2007/165-2/p04). In *Annals of Mathematics* **165**(2), pp 547-565, 2007.

> **Comments:**
> **username_16**: theorem (Adamczewski & Bugeaud [3]) may be wrong or be misunderstood  

---

### Answer by username_3 on 2010-11-23. Score: 6

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](https://cstheory.stackexchange.com/questions/149/applications-of-tcs-to-classical-mathematics/157#157)'s answer.


---

### Answer by username_15 on 2014-01-11. Score: 5

In his paper [**Straight Line Programs and Torsion Points on Elliptic Curves**](http://www.cs.ou.edu/~qcheng/paper/BSS.pdf), 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 by username_17 on 2013-10-23. Score: 2

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.


---

