# Impact of Grothendieck's program on TCS

Grothendieck has passed away. He had massive impact on 20th century mathematics continuing into the 21st century. This question is asked somewhat in the style/spirit, for example, of Alan Turing's Contributions to Computer Science.

What are Grothendieck's major influences on theoretical computer science?

• obituary in English / ABCNews
– vzn
Nov 14 '14 at 19:04
• Maybe this is relevant: Is Grothendieck a computer? Nov 14 '14 at 20:28
• I hope someone from theory B writes about category theory and Grothendieck topologies (or is his work there not relevant to computer science?). Nov 14 '14 at 20:41
• fyi some sketch/ outline of an answer from reddit / "frobenius"
– vzn
Nov 14 '14 at 21:22
• Maybe @AndrejBauer can help. Nov 16 '14 at 9:29

Grothendieck's inequality, from his days in functional analysis, was initially proved to relate fundamental norms on tensor product spaces. Grothendieck called the inequality "the fundamental theorem of the metric theory of tensor product spaces", and published it in a now famous paper in 1958, in French, in a limited circulation Brazilian journal. The paper was largely ignored for 15 years, until it was rediscovered by Lindenstrauss and Pelczynski (after Grothendieck had left functional analysis). They gave many reformulations of the paper's main results, related it to research on absolutely summing operators and factorization norms, and observed that Grothendieck had solved "open" problems which had been raised after the paper was published. Pisier gives a very detailed account of the inequality, its variants, and its tremendous influence on functional analysis in his survey.

Grothendieck's inequality is very naturally expressed in the language of combinatorial optimization and approximation algorithms. It says that the non-convex, NP-hard optimization problem $$\max\{x^TAy: x \in \{-1, 1\}^m, y \in \{-1, 1\}^n\}$$ is approximated up to a fixed constant by its semidefinite relaxation $$\max\{\sum_{i,j}{a_{ij}\langle u_i, v_j\rangle}: u_1, \ldots, u_m, v_1, \ldots, v_n \in \mathbb{S}^{n+m-1}\},$$ where $\mathbb{S}^{n+m-1}$ is the unit sphere in $\mathbb{R}^{n+m}$. Proofs of the inequality give "rounding algorithms", and in fact the Goemans-Williamson random hyperplane rounding does the job (but gives a suboptimal constant). However, Grothendieck's inequality is interesting because the analysis of the rounding algorithm has to be "global", i.e. look at all terms of the objective function together.

Having said this, it should not be surprising that Grothendiecks's inequality has found a second (third? fourth?) life in computer science. Khot and Naor survey its multiple applications and connections to combinatorial optimization.

The story does not end there. The inequality is related to Bell inequality violations in quantum mechanics (see Pisier's paper), has been used by Linial and Shraibman in work on communication complexity, and even turned out useful in work on private data analysis (shameless plug).

• Here is another text on Grothendieck's inequality and CS. But I am not qualified to comment. Nov 14 '14 at 20:44
• A lecture by Giles Pisier at IHES might also be interesting: dailymotion.com/video/… (unfortunately it's interrupted by annoying ads). Nov 14 '14 at 21:37

Grothendieck's impact can be felt in type theory and logic. For instance, Bart Jacobs' 700+ page volume Categorical Logic and Type Theory gives a uniform treatment of various type theories ($X$-type theory, where $X\subseteq \{ \text{simple},$ $\text{dependent},$ $\text{polymorphic},$ $\text{higher-order}\}$) based on the categorical notion of Grothendieck fibrations (also called a cartesian fibrations). Similarly, the notion of Topos, also due to Grothendieck, plays a heavy role in providing categorical semantics to logics and type theories, which is of interest to logicians and theoretical computer scientists alike.

• $\subseteq$ over $\in$ because it comes first in setting up an elementary topos? Nov 17 '14 at 23:34
• @NikolajK There is no real formal meaning to my use of $\subseteq$ over $\in$ -- Chapter 11 of the book addresses Higher-order Dependent Type Theory, for instance. Nov 18 '14 at 8:38

Any applications of $p$-adic cohomology, etale cohomology in point counting formulas for algebraic varieties has roots in his work.

I am guessing Mulmuley's vision of generalization of Riemann hypothesis over finite fields coming from the Weil conjectures can be thought of as asking questions which originally had fruitful results from Grothendieck's etale cohomology.

• Are these applications in theoretical computer science? It all sounds like mathematics to me – or probably that other bit of TCS. Nov 16 '14 at 21:19
• Yes. Cryptography and coding theory consistently use point counting and Gauss sums. Mulmuley's program is the only one that is known to overcome all known obstructions for $VNP$ versus $VP$ separation. There probably are many other applications as well.
– Mr.
Nov 16 '14 at 21:22