<p>There are many such examples. When I first learned complexity theory, I found it surprising that basic theorems about roots of polynomials (such as the Schwartz-Zippel-DeMillo-Lipton Lemma) had anything to do with the question of whether interactive proofs can simulate polynomial space ($IP = PSPACE$). Of course, those properties of polynomials had already been used in prior work, and nowadays the use of "polynomializing" computations has become quite standard in complexity theory.</p>

CC BY-SA 2.5
2010-10-04T21:31:55.813Z
I also enjoy the polynomial trick for finding perfect matchings in bipartite graphs by randomly sampling the determinant (thanks, Lovász).
Derrick Stolee
CC BY-SA 2.5
2010-10-04T21:04:38.227Z
2010-10-04T21:04:38.227Z
Ryan Williams
<p>Representation theory of finite groups is used in the <a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.39">Cohn-Kleinberg-Szegedy-Umans approach to matrix multiplication</a>.
They show that if families of wreath products of abelian with symmetric groups satisfying certain conditions exist, then there are matrix multiplication algorithms of quadratic complexity.</p>

<p>Representation theory (of algebraic groups) also shows up in Mulmuley and Sohoni's <a href="http://ramakrishnadas.cs.uchicago.edu/">geometric complexity theory</a> approach to lower bounds.  It's not clear yet if this counts as an application, since no new complexity results have yet been proven with this approach, but at least an interesting connection has been made between two areas that at first blush seem totally unrelated.</p>

CC BY-SA 2.5
2010-10-05T16:13:30.910Z
2010-12-23T01:39:27.460Z
2010-12-23T01:39:27.460Z
Joshua Grochow
<p>Another beautiful idea: Yao's idea to use minimax principles and the proof that mixed games have an equilibrium (essentially linear programming duality) to show lower bounds on randomized algorithms (by instead constructing a distribution over inputs to a deterministic algorithm).</p>

CC BY-SA 2.5
2010-10-05T00:10:25.920Z
Also Noam Nisan's proof to Russell Impagliazzo's Hard Core Lemma (in Russell's original paper)
Dana Moshkovitz
CC BY-SA 4.0
2010-10-04T21:48:15.497Z
2022-11-22T19:26:53.907Z
2022-11-22T19:26:53.907Z
Suresh Venkat
<p>Approximation theory (which deals with approximating possibly complicated or unnatural real-valued functions by simple functions, such as low-degree polynomials) has had many uses in Circuit complexity, Quantum query complexity, Pseudorandomness etc.</p>

<p>I think one of the coolest applications of tools from this area comes from <a href="http://knight.cis.temple.edu/~beigel/papers/brs-pp-jcss.html">this</a> paper of Beigel, Reingold, and Spielman, where they showed that the complexity class PP is closed under intersection by using the fact that the sign function can be approximated by a low-degree rational function.</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.3215&amp;rep=rep1&amp;type=pdf">Nisan and Szegedy</a> and <a href="http://doi.acm.org/10.1145/129712.129758">Paturi</a> showed lower bounds for approximating symmetric functions by low-degree polynomials. This method is frequently used in proving Quantum query complexity lower bounds. See Scott Aaronson's <a href="http://stellar.mit.edu/S/course/6/fa10/6.845/courseMaterial/topics/topic3/lectureNotes/qctlec10/qctlec10.pdf">lecture notes</a>, for example.</p>

CC BY-SA 2.5
2010-10-04T23:16:53.497Z
2010-10-04T23:16:53.497Z
Srikanth
<p>Fixed point theorems are all over the place...</p>

<p>But a pretty surprising example of geometry popping from nowhere is the effective comparison result. Here, given a partial order defined over a set of $n$ elements, consider the set of permutations of the objects that are compatible with the given partial order. The question is to pick the most effective comparison to do next; that is, what is the comparison that would shrink the number of permutations compatible with the new partial order (of course, there are two possible partial orders, depending on the result of this single comparison). It is known that there is always a comparison that shrinks the number of permutations by a constant factor (thus, you can sort in $O(\log n!)$ comparisons, duh). The proof of this fact goes via the geometry of high dimensional polytopes. Specifically, the proof uses the Brunn-Minkowski inequality. A good presentation of this is in Matousek book on Lectures on Discrete Geometry (Section 12.3). The original proof is by Kahn and Linial, from <a href="http://www.cs.huji.ac.il/~nati/PAPERS/brunn_minkowski.pdf">here</a>.</p>

CC BY-SA 4.0
2022-01-06T02:07:36.507Z
And, given Stirling's Approximation, that `log n!` reduces to `log e^(n log n)`, and then to (drum roll)... `n log n`.
TLW
CC BY-SA 2.5
2010-10-05T03:10:38.400Z
2010-10-06T12:24:45.567Z
2010-10-06T12:24:45.567Z
Sariel Har-Peled
<p>There are plenty of uses of <strong>information theory</strong> in theoretical computer science:
e.g., in proving lower bounds for locally decodeable codes (see Katz and Trevisan), in Raz's proof of the parallel repetition theorem, in communication complexity (see, for example, the thread of work on compression of communication, e.g., the relatively recent work of Barak, Braverman, Chen and Rao, and the references there), and so much more work. </p>

CC BY-SA 2.5
2010-10-28T17:42:40.363Z
But are these uses really "unrelated"?  At least from a naive point of view, it seems to me that information theory is one of the first areas that come to mind when one first hears the definition of, say, locally decodable codes.
arnab
CC BY-SA 2.5
2010-10-29T02:05:37.833Z
I agree that information theory is related to codes, for example, and codes are related to TCS. Parallel repetition is maybe a stronger example: why would you think of using it for soundness amplification for PCPs?
Dana Moshkovitz
CC BY-SA 2.5
2010-10-29T02:52:31.330Z
Yes, I completely agree that parallel repetition is a surprising example.
arnab
CC BY-SA 2.5
2010-10-28T17:23:35.803Z
2010-10-28T17:23:35.803Z
Dana Moshkovitz
<p>In retrospect, this may be obvious, but I've always been fond of Steele, Yao, and Ben-Or's application of the Oleinik-Petrovsky/Milnor/Thom theorem (bounding the Betti numbers of real semi-algebraic sets) to prove lower bounds in the algebraic decision tree and algebraic computation tree models of computation.</p>

CC BY-SA 2.5
2010-10-05T03:34:29.837Z
The "in retrospect, it's obvious" kind of results are the best kind of applications.  Hindsight is 20/20.
Derrick Stolee
CC BY-SA 2.5
2010-10-05T02:54:55.380Z
2010-10-05T02:54:55.380Z
Jeffε
<p>I have an example from a work I co-authored with Noga Alon and Muli Safra a few years ago:</p>
<p>Noga used algebraic topology fixed-point theorems to prove the &quot;Necklace Splitting Theorem&quot;: if you have a necklace with beads of <span class="math-container">$t$</span> types and you want to divide parts of it between <span class="math-container">$b$</span> people so each gets the same number of beads from each type (assume <span class="math-container">$b$</span> divides <span class="math-container">$t$</span>), you can always do that by cutting the necklace in at most <span class="math-container">$(b-1)t$</span> places.</p>
<p>We used this theorem to construct a combinatorial object that we used for proving the hardness of approximating Set-Cover.</p>
<p>Some more info is here:
<a href="http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest.html" rel="nofollow noreferrer">http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest.html</a></p>

CC BY-SA 4.0
2010-10-05T00:03:21.380Z
2022-11-22T19:25:55.123Z
2022-11-22T19:25:55.123Z
Dana Moshkovitz
<p>One of my favorite results is the use of topological arguments in <a href="https://en.wikipedia.org/wiki/Kneser_graph" rel="nofollow noreferrer">Lovász's proof of the Kneser conjecture</a>, and the use of topological (<em>and group-theoretic</em>) methods in the <a href="https://doi.org/10.1007/BF02579140" rel="nofollow noreferrer" title="A topological approach to evasiveness. Combinatorica 4, 297–306 (1984)">Kahn–Saks–Sturtevant attack</a> on the strong Aandera–Rosenberg–Karp conjecture on evasiveness.</p>

CC BY-SA 3.0
2011-10-24T23:57:40.737Z
I was wondering if it's worth "waking up" this thread after a year to point out a reference..but then it's a great thread so why not. The Lovasz result and other results, as well as an intro to "algebraic topology for combinatorialists" can be found in Matousek's monograph: http://kam.mff.cuni.cz/~matousek/akt.html
Sasho Nikolov
CC BY-SA 2.5
2010-10-04T20:59:21.183Z
+1. The use of topological arguments in proving combinatorial statements is truly epic. Interested readers can find some more info here: http://en.wikipedia.org/wiki/Topological_combinatorics
Robin Kothari
CC BY-SA 2.5
2010-10-05T03:57:00.930Z
@Robin: Or how about geometric arguments? The main theorem of the classic Bayer-Diaconis paper on dovetail shuffling was discovered by thinking of the shuffle as a volume-preserving transformation (the baker's map: double and fold (mod 1) along each axis) of the 52-cube. Unfortunately they removed most traces of the geometric intuition from the final paper by replacing it with discrete combinatorics.
Per Vognsen
CC BY-SA 2.5
2010-10-05T03:59:58.350Z
@Per Vognsen: I am not familiar with that work, so thanks for the pointer. I'll take a look at it.
Robin Kothari
CC BY-SA 2.5
2010-10-05T04:05:28.557Z
@Robin: It's a great paper! It's also a nice example of the general idea of embedding a discrete problem in a continuous problem: doubling and folding is a continuous analogue of a discrete 2-shuffle, which cuts the deck in half and interleaves. Dana Moshkovitz's example of necklace splitting fits a similar pattern.
Per Vognsen
CC BY-SA 2.5
2010-10-05T15:59:07.407Z
You might want to add "topological *and group-theoretic* methods" for Kahn-Saks-Sturtevant.  They do, after all, crucially use group actions on simplicial complexes.
Joshua Grochow
CC BY-SA 2.5
2010-10-05T16:13:31.113Z
Good point, Joshua.
Suresh Venkat
CC BY-SA 4.0
2010-10-04T20:03:31.473Z
2022-11-22T17:36:03.130Z
2022-11-22T17:36:03.130Z
Suresh Venkat
<p>Alon and Naor used Grothendieck's inequality to prove an <a href="http://portal.acm.org/citation.cfm?id=1007352.1007371">approximation algorithm on the max-cut problem</a>. I think that there are subsequent works on that topic but I'm not an expert.</p>

<p>Interestingly, the same theorem was used by Cleve, Hoyer, Toner and Watrous to analyze quantum XOR games, and Linial and Shraibman used it for quantum communication complexity. Up to my knowledge, the relation between Grothendieck's inequality and the foundation of quantum physics was discovered by Tsirelson in 85, but the two results I mentioned specifically address computer science.</p>

CC BY-SA 3.0
2013-04-30T18:49:02.743Z
Uhm, this is not accurate. Alon and Naor approximated the cut norm of a matrix - this is related to max cut but not the same.
Sasho Nikolov
CC BY-SA 2.5
2010-10-05T12:26:00.070Z
2010-10-05T12:26:00.070Z
Marc
<p>A good example is Barrington's theorem:</p>

<blockquote>
  <p>If a boolean function $f$ is
  computable by a circuit of depth $d$,
  then $f$ is computable by a branching
  program of width 5 and length $4^d$.</p>
</blockquote>

<p><a href="http://blog.computationalcomplexity.org/2008/11/barringtons-theorem.html?showComment=1226437380000#c5698134130239477112">The proof</a> uses the group $S_5$ (because it has two elements that are conjugate to each other and to their commutator), but it can be generalized to work on any non-solvable group.</p>

CC BY-SA 2.5
2010-10-30T06:51:04.020Z
2010-10-30T06:51:04.020Z
didest
<p>Shameless plug: use of the Isotropic conjecture (and convex geometry in general) in designing approximately optimal differentially private mechanisms for linear queries in my <a href="http://arxiv.org/abs/0907.3754">work</a> with <a href="http://www.cs.princeton.edu/~mhardt/">Moritz Hardt</a>.</p>

<p>To partially answer Suresh's question above, I think the original question is a slightly tricky one because of the "not normally considered to apply in computer science". Some of these techniques which may seem originally "unrelated" become "normal" over time. So the most successful of these techniques (e.g. Fourier analysis in Kahn-Kalai-Linial, metric embeddings in Linial-London-Rabinovich) are not valid answers any more.</p>

CC BY-SA 2.5
2010-10-05T08:45:28.113Z
Perhaps I'll reword the question to address this.
Derrick Stolee
CC BY-SA 2.5
2010-10-05T05:52:08.670Z
2010-10-05T05:52:08.670Z
Kunal
<p><a href="http://www.cs.cmu.edu/~sleator/papers/rotation-distance.pdf">Sleator, Tarjan and Thurston</a> proved the existence of an infinite family of pairs of binary search trees with <code>n</code> vertices and rotation distance <code>2n-6</code> using hyperbolic geometry.</p>

CC BY-SA 3.0
2011-08-12T06:46:26.077Z
2011-08-12T06:46:26.077Z
zotachidil
<p>Additive combinatorics / number theory was used a lot in extractor literature. I think the first instances come from noticing that Paley graphs could be used as good extractors, and some open questions in additive number theory would imply better ones. Earliest reference I know is Zuckerman 1990 (see his <a href="http://www.cs.utexas.edu/~diz/pubs/thesis.ps">thesis</a>), but in last few years this has been an active area with interesting back and forth between TCS and additive combinatorics. (One of the highlights being <a href="http://www.cs.princeton.edu/~zdvir/papers/Dvir09.pdf">Dvir's proof</a> of the finite field Kakeya  conjecture, but this is of course a TCS contribution to math and not the other way around.)  A-priori it's not clear why these kind of mathematical questions, on sums and products of sets, would be important for CS.</p>

CC BY-SA 2.5
2010-10-29T05:09:32.430Z
another good example in this vein is the recent use of the density Hales-Jewitt conjecture to prove a nonlinear lower bound on the epsilon net for a range space of VC dimension 2.
Suresh Venkat
CC BY-SA 2.5
2010-10-29T04:38:08.960Z
2010-10-29T04:38:08.960Z
Boaz Barak
<p>Additive combinatorics used to construct an explicit RIP matrix with $o(k^2)$ rows:</p>

<p>Jean Bourgain, Stephen J. Dilworth, Kevin Ford, Sergei Konyagin, Denka Kutzarova: Breaking the $k^2$ barrier for explicit RIP matrices. STOC 2011: 637-644.</p>

<p>Linear algebra used to sparsify graphs:</p>

<p>Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava: Twice-ramanujan sparsifiers. STOC 2009: 255-262.</p>

CC BY-SA 3.0
2011-08-23T14:25:21.880Z
2011-08-23T14:25:21.880Z
Jelani Nelson
<p>This may or may not count, but recently Zermelo-Fraenkel with atoms (ZFA) and Fraenkel-Mostowski (FM) set theories have been applied to the study of abstract syntax with name binding.  ZFA was introduced in the early 20th century as a tool for proving the independence of CH and then forgotten about, but rediscovered in the late 1990s by two computer scientists---Gabbay and Pitts---studying something completely unconnected.</p>

<p>See <a href="http://www.gabbay.org.uk/papers/fountl.pdf">this</a> survey paper for instance.</p>

CC BY-SA 2.5
2010-10-30T21:51:56.673Z
2010-10-31T00:37:02.900Z
2010-10-31T00:37:02.900Z
Dominic Mulligan
<p>Number theory was used to develop RSA and other public-key cryptographic schemes.</p>

CC BY-SA 3.0
2011-04-29T21:47:52.520Z
2011-04-29T21:47:52.520Z
Antonio Valerio Miceli-Barone
<p>Kahn and Kim's application of graph entropy to to sorting under partial information (http://portal.acm.org/citation.cfm?id=129731). They gave the first polynomial time algorithm that performs the information theoretically optimal (up to constants) number of comparisons. The paper is a small field trip in mathematics, using some classical combinatorial arguments, together with convex geometry, graph entropy, and convex programming. There is a more recent simpler algorithm, but we still do now know how to analyze it without graph entropy.</p>

CC BY-SA 3.0
2011-04-29T18:58:00.813Z
2011-04-29T18:58:00.813Z
Sasho Nikolov
<p>Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou got the <a href="http://en.wikipedia.org/wiki/G%C3%B6del_Prize">Godel prize in 2004</a> for their use of algebraic topology in the study of some problems in distributed computing.</p>

CC BY-SA 2.5
2010-10-04T22:32:47.417Z
2010-10-04T22:32:47.417Z
Warren Schudy
<p>Please list examples where a theorem from mathematics which was not normally considered to apply in computer science was first used to prove a result in computer science.  The best examples are those where the connection was not obvious, but once it was discovered, it is clearly the "right way" to do it.</p>

<p>This is the opposite direction of the question <a href="https://cstheory.stackexchange.com/questions/149/applications-of-tcs-to-classical-mathematics">Applications of TCS to classical mathematics?</a></p>

<p>For example, see <a href="http://www.eccc.uni-trier.de/report/2010/151/" rel="noreferrer">"Green's Theorem and Isolation in Planar Graphs"</a>, where an isolation theorem (which was already known using a technical proof) is re-proven using Green's Theorem from multivariate calculus. </p>

<p>What other examples are there?</p>

CC BY-SA 2.5
2010-10-05T04:15:09.573Z
Surprising how many examples are about topology and geometry. Are we just more surprised by these two topics ?
Suresh Venkat
CC BY-SA 2.5
2010-10-05T14:12:04.177Z
Once enough examples of Area X are given, does that make Area X no longer "unrelated"?
András Salamon
<reference-request><soft-question><big-list><topology>
Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?
Derrick Stolee
# Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?

(Asked by: username_0 on 2010-10-04)

Please list examples where a theorem from mathematics which was not normally considered to apply in computer science was first used to prove a result in computer science. The best examples are those where the connection was not obvious, but once it was discovered, it is clearly the "right way" to do it.

This is the opposite direction of the question [Applications of TCS to classical mathematics?](https://cstheory.stackexchange.com/questions/149/applications-of-tcs-to-classical-mathematics)

For example, see ["Green's Theorem and Isolation in Planar Graphs"](http://www.eccc.uni-trier.de/report/2010/151/), where an isolation theorem (which was already known using a technical proof) is re-proven using Green's Theorem from multivariate calculus.

What other examples are there?

**Tags:** reference-request, soft-question, big-list, topology
> **Comments:**
> **username_1**: Surprising how many examples are about topology and geometry. Are we just more surprised by these two topics ?  
> **username_2**: Once enough examples of Area X are given, does that make Area X no longer "unrelated"?  

---

## 19 answers

### Answer by username_22 on 2010-10-04. Score: 41 | Accepted answer

Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou got the [Godel prize in 2004](http://en.wikipedia.org/wiki/G%C3%B6del_Prize) for their use of algebraic topology in the study of some problems in distributed computing.


---

### Answer by username_10 on 2010-10-05. Score: 27

In retrospect, this may be obvious, but I've always been fond of Steele, Yao, and Ben-Or's application of the Oleinik-Petrovsky/Milnor/Thom theorem (bounding the Betti numbers of real semi-algebraic sets) to prove lower bounds in the algebraic decision tree and algebraic computation tree models of computation.

> **Comments:**
> **username_0**: The "in retrospect, it's obvious" kind of results are the best kind of applications.  Hindsight is 20/20.  

---

### Answer by username_5 on 2010-10-05. Score: 26

I have an example from a work I co-authored with Noga Alon and Muli Safra a few years ago:

Noga used algebraic topology fixed-point theorems to prove the "Necklace Splitting Theorem": if you have a necklace with beads of $t$ types and you want to divide parts of it between $b$ people so each gets the same number of beads from each type (assume $b$ divides $t$), you can always do that by cutting the necklace in at most $(b-1)t$ places.

We used this theorem to construct a combinatorial object that we used for proving the hardness of approximating Set-Cover.

Some more info is here:
<http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest.html>


---

### Answer by username_1 on 2010-10-04. Score: 25

One of my favorite results is the use of topological arguments in [Lovász's proof of the Kneser conjecture](https://en.wikipedia.org/wiki/Kneser_graph), and the use of topological (*and group-theoretic*) methods in the [Kahn–Saks–Sturtevant attack](https://doi.org/10.1007/BF02579140 "A topological approach to evasiveness. Combinatorica 4, 297–306 (1984)") on the strong Aandera–Rosenberg–Karp conjecture on evasiveness.

> **Comments:**
> **username_12**: +1. The use of topological arguments in proving combinatorial statements is truly epic. Interested readers can find some more info here: http://en.wikipedia.org/wiki/Topological_combinatorics  
> **username_13**: @Robin: Or how about geometric arguments? The main theorem of the classic Bayer-Diaconis paper on dovetail shuffling was discovered by thinking of the shuffle as a volume-preserving transformation (the baker's map: double and fold (mod 1) along each axis) of the 52-cube. Unfortunately they removed most traces of the geometric intuition from the final paper by replacing it with discrete combinatorics.  
> **username_12**: @Per Vognsen: I am not familiar with that work, so thanks for the pointer. I'll take a look at it.  
> **username_13**: @Robin: It's a great paper! It's also a nice example of the general idea of embedding a discrete problem in a continuous problem: doubling and folding is a continuous analogue of a discrete 2-shuffle, which cuts the deck in half and interleaves. Dana Moshkovitz's example of necklace splitting fits a similar pattern.  
> **username_4**: You might want to add "topological *and group-theoretic* methods" for Kahn-Saks-Sturtevant.  They do, after all, crucially use group actions on simplicial complexes.  
> **username_1**: Good point, Joshua.  
> **username_11**: I was wondering if it's worth "waking up" this thread after a year to point out a reference..but then it's a great thread so why not. The Lovasz result and other results, as well as an intro to "algebraic topology for combinatorialists" can be found in Matousek's monograph: http://kam.mff.cuni.cz/~matousek/akt.html  

---

### Answer by username_3 on 2010-10-04. Score: 23

There are many such examples. When I first learned complexity theory, I found it surprising that basic theorems about roots of polynomials (such as the Schwartz-Zippel-DeMillo-Lipton Lemma) had anything to do with the question of whether interactive proofs can simulate polynomial space ($IP = PSPACE$). Of course, those properties of polynomials had already been used in prior work, and nowadays the use of "polynomializing" computations has become quite standard in complexity theory.

> **Comments:**
> **username_0**: I also enjoy the polynomial trick for finding perfect matchings in bipartite graphs by randomly sampling the determinant (thanks, Lovász).  

---

### Answer by username_4 on 2010-10-05. Score: 23

Representation theory of finite groups is used in the [Cohn-Kleinberg-Szegedy-Umans approach to matrix multiplication](http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.39).
They show that if families of wreath products of abelian with symmetric groups satisfying certain conditions exist, then there are matrix multiplication algorithms of quadratic complexity.

Representation theory (of algebraic groups) also shows up in Mulmuley and Sohoni's [geometric complexity theory](http://ramakrishnadas.cs.uchicago.edu/) approach to lower bounds. It's not clear yet if this counts as an application, since no new complexity results have yet been proven with this approach, but at least an interesting connection has been made between two areas that at first blush seem totally unrelated.


---

### Answer by username_1 on 2010-10-04. Score: 22

Another beautiful idea: Yao's idea to use minimax principles and the proof that mixed games have an equilibrium (essentially linear programming duality) to show lower bounds on randomized algorithms (by instead constructing a distribution over inputs to a deterministic algorithm).

> **Comments:**
> **username_5**: Also Noam Nisan's proof to Russell Impagliazzo's Hard Core Lemma (in Russell's original paper)  

---

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

Approximation theory (which deals with approximating possibly complicated or unnatural real-valued functions by simple functions, such as low-degree polynomials) has had many uses in Circuit complexity, Quantum query complexity, Pseudorandomness etc.

I think one of the coolest applications of tools from this area comes from [this](http://knight.cis.temple.edu/~beigel/papers/brs-pp-jcss.html) paper of Beigel, Reingold, and Spielman, where they showed that the complexity class PP is closed under intersection by using the fact that the sign function can be approximated by a low-degree rational function.

[Nisan and Szegedy](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.3215&rep=rep1&type=pdf) and [Paturi](http://doi.acm.org/10.1145/129712.129758) showed lower bounds for approximating symmetric functions by low-degree polynomials. This method is frequently used in proving Quantum query complexity lower bounds. See Scott Aaronson's [lecture notes](http://stellar.mit.edu/S/course/6/fa10/6.845/courseMaterial/topics/topic3/lectureNotes/qctlec10/qctlec10.pdf), for example.


---

### Answer by username_7 on 2010-10-05. Score: 18

Fixed point theorems are all over the place...

But a pretty surprising example of geometry popping from nowhere is the effective comparison result. Here, given a partial order defined over a set of $n$ elements, consider the set of permutations of the objects that are compatible with the given partial order. The question is to pick the most effective comparison to do next; that is, what is the comparison that would shrink the number of permutations compatible with the new partial order (of course, there are two possible partial orders, depending on the result of this single comparison). It is known that there is always a comparison that shrinks the number of permutations by a constant factor (thus, you can sort in $O(\log n!)$ comparisons, duh). The proof of this fact goes via the geometry of high dimensional polytopes. Specifically, the proof uses the Brunn-Minkowski inequality. A good presentation of this is in Matousek book on Lectures on Discrete Geometry (Section 12.3). The original proof is by Kahn and Linial, from [here](http://www.cs.huji.ac.il/~nati/PAPERS/brunn_minkowski.pdf).

> **Comments:**
> **username_8**: And, given Stirling's Approximation, that `log n!` reduces to `log e^(n log n)`, and then to (drum roll)... `n log n`.  

---

### Answer by username_5 on 2010-10-28. Score: 16

There are plenty of uses of **information theory** in theoretical computer science:
e.g., in proving lower bounds for locally decodeable codes (see Katz and Trevisan), in Raz's proof of the parallel repetition theorem, in communication complexity (see, for example, the thread of work on compression of communication, e.g., the relatively recent work of Barak, Braverman, Chen and Rao, and the references there), and so much more work.

> **Comments:**
> **username_9**: But are these uses really "unrelated"?  At least from a naive point of view, it seems to me that information theory is one of the first areas that come to mind when one first hears the definition of, say, locally decodable codes.  
> **username_5**: I agree that information theory is related to codes, for example, and codes are related to TCS. Parallel repetition is maybe a stronger example: why would you think of using it for soundness amplification for PCPs?  
> **username_9**: Yes, I completely agree that parallel repetition is a surprising example.  

---

### Answer by username_14 on 2010-10-05. Score: 14

Alon and Naor used Grothendieck's inequality to prove an [approximation algorithm on the max-cut problem](http://portal.acm.org/citation.cfm?id=1007352.1007371). I think that there are subsequent works on that topic but I'm not an expert.

Interestingly, the same theorem was used by Cleve, Hoyer, Toner and Watrous to analyze quantum XOR games, and Linial and Shraibman used it for quantum communication complexity. Up to my knowledge, the relation between Grothendieck's inequality and the foundation of quantum physics was discovered by Tsirelson in 85, but the two results I mentioned specifically address computer science.

> **Comments:**
> **username_11**: Uhm, this is not accurate. Alon and Naor approximated the cut norm of a matrix - this is related to max cut but not the same.  

---

### Answer by username_15 on 2010-10-30. Score: 14

A good example is Barrington's theorem:

> If a boolean function $f$ is
> computable by a circuit of depth $d$,
> then $f$ is computable by a branching
> program of width 5 and length $4^d$.

[The proof](http://blog.computationalcomplexity.org/2008/11/barringtons-theorem.html?showComment=1226437380000#c5698134130239477112) uses the group $S\_5$ (because it has two elements that are conjugate to each other and to their commutator), but it can be generalized to work on any non-solvable group.


---

### Answer by username_16 on 2010-10-05. Score: 12

Shameless plug: use of the Isotropic conjecture (and convex geometry in general) in designing approximately optimal differentially private mechanisms for linear queries in my [work](http://arxiv.org/abs/0907.3754) with [Moritz Hardt](http://www.cs.princeton.edu/~mhardt/).

To partially answer Suresh's question above, I think the original question is a slightly tricky one because of the "not normally considered to apply in computer science". Some of these techniques which may seem originally "unrelated" become "normal" over time. So the most successful of these techniques (e.g. Fourier analysis in Kahn-Kalai-Linial, metric embeddings in Linial-London-Rabinovich) are not valid answers any more.

> **Comments:**
> **username_0**: Perhaps I'll reword the question to address this.  

---

### Answer by username_17 on 2011-08-12. Score: 12

[Sleator, Tarjan and Thurston](http://www.cs.cmu.edu/~sleator/papers/rotation-distance.pdf) proved the existence of an infinite family of pairs of binary search trees with `n` vertices and rotation distance `2n-6` using hyperbolic geometry.


---

### Answer by username_18 on 2010-10-29. Score: 12

Additive combinatorics / number theory was used a lot in extractor literature. I think the first instances come from noticing that Paley graphs could be used as good extractors, and some open questions in additive number theory would imply better ones. Earliest reference I know is Zuckerman 1990 (see his [thesis](http://www.cs.utexas.edu/~diz/pubs/thesis.ps)), but in last few years this has been an active area with interesting back and forth between TCS and additive combinatorics. (One of the highlights being [Dvir's proof](http://www.cs.princeton.edu/~zdvir/papers/Dvir09.pdf) of the finite field Kakeya conjecture, but this is of course a TCS contribution to math and not the other way around.) A-priori it's not clear why these kind of mathematical questions, on sums and products of sets, would be important for CS.

> **Comments:**
> **username_1**: another good example in this vein is the recent use of the density Hales-Jewitt conjecture to prove a nonlinear lower bound on the epsilon net for a range space of VC dimension 2.  

---

### Answer by username_19 on 2011-08-23. Score: 8

Additive combinatorics used to construct an explicit RIP matrix with $o(k^2)$ rows:

Jean Bourgain, Stephen J. Dilworth, Kevin Ford, Sergei Konyagin, Denka Kutzarova: Breaking the $k^2$ barrier for explicit RIP matrices. STOC 2011: 637-644.

Linear algebra used to sparsify graphs:

Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava: Twice-ramanujan sparsifiers. STOC 2009: 255-262.


---

### Answer by username_20 on 2010-10-30. Score: 7

This may or may not count, but recently Zermelo-Fraenkel with atoms (ZFA) and Fraenkel-Mostowski (FM) set theories have been applied to the study of abstract syntax with name binding. ZFA was introduced in the early 20th century as a tool for proving the independence of CH and then forgotten about, but rediscovered in the late 1990s by two computer scientists---Gabbay and Pitts---studying something completely unconnected.

See [this](http://www.gabbay.org.uk/papers/fountl.pdf) survey paper for instance.


---

### Answer by username_21 on 2011-04-29. Score: 5

Number theory was used to develop RSA and other public-key cryptographic schemes.


---

### Answer by username_11 on 2011-04-29. Score: 4

Kahn and Kim's application of graph entropy to to sorting under partial information (http://portal.acm.org/citation.cfm?id=129731). They gave the first polynomial time algorithm that performs the information theoretically optimal (up to constants) number of comparisons. The paper is a small field trip in mathematics, using some classical combinatorial arguments, together with convex geometry, graph entropy, and convex programming. There is a more recent simpler algorithm, but we still do now know how to analyze it without graph entropy.


---

