Examples of “Unrelated” Mathematics Playing a Fundamental Role in TCS?

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?

For example, see "Green's Theorem and Isolation in Planar Graphs", 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?

-
Community wiki. –  Dave Clarke Oct 4 '10 at 18:55
Community wiki is now in place. –  Derrick Stolee Oct 4 '10 at 18:57
Surprising how many examples are about topology and geometry. Are we just more surprised by these two topics ? –  Suresh Venkat Oct 5 '10 at 4:15
Once enough examples of Area X are given, does that make Area X no longer "unrelated"? –  András Salamon Oct 5 '10 at 14:12

Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou got the Godel prize in 2004 for their use of algebraic topology in the study of some problems in distributed computing.

-
This is a great example! –  Ryan Williams Oct 4 '10 at 22:46

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.

-
The "in retrospect, it's obvious" kind of results are the best kind of applications. Hindsight is 20/20. –  Derrick Stolee Oct 5 '10 at 3:34

One of my favorite results is the use of topological arguments in Lovasz's proof of the Kneser conjecture, and the use of topological (and group-theoretic) methods in the Kahn-Saks-Sturtevant attack on the strong Aandera-Rosenberg-Karp conjecture on evasiveness.

-
+1. The use of topological arguments in proving combinatorial statements is truly epic. Interested readers can find some more info here: en.wikipedia.org/wiki/Topological_combinatorics –  Robin Kothari Oct 4 '10 at 20:59
@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 Oct 5 '10 at 3:57
@Per Vognsen: I am not familiar with that work, so thanks for the pointer. I'll take a look at it. –  Robin Kothari Oct 5 '10 at 3:59
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 Oct 5 '10 at 15:59
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: kam.mff.cuni.cz/~matousek/akt.html –  Sasho Nikolov Oct 24 '11 at 23:57

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.

-

Representation theory of finite groups is used in the Cohn-Kleinberg-Szegedy-Umans approach to matrix multiplication. 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 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.

-

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

-
Also Noam Nisan's proof to Russell Impagliazzo's Hard Core Lemma (in Russell's original paper) –  Dana Moshkovitz Oct 5 '10 at 0:10

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 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 and Paturi 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, for example.

-

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.

-
I also enjoy the polynomial trick for finding perfect matchings in bipartite graphs by randomly sampling the determinant (thanks, Lovász). –  Derrick Stolee Oct 4 '10 at 21:31

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.

-

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.

-
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 Oct 28 '10 at 17:42
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 Oct 29 '10 at 2:05
Yes, I completely agree that parallel repetition is a surprising example. –  arnab Oct 29 '10 at 2:52

Alon and Naor used Grothendieck's inequality to prove an approximation algorithm on the max-cut problem. 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.

-
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 Apr 30 '13 at 18:49

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

-

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 with Moritz Hardt.

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.

-
Perhaps I'll reword the question to address this. –  Derrick Stolee Oct 5 '10 at 8:45

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

-
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 Oct 29 '10 at 5:09

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 survey paper for instance.

-

Sleator, Tarjan and Thurston proved the existence of an infinite family of pairs of binary search trees with n vertices and rotation distance 2n-6 using hyperbolic geometry.

-

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.

-

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.

-

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

-

The discovery of Karatsuba multiplication was surprising.

-
Gauss would disagree. –  JɛﬀE Aug 2 '12 at 22:13