<p>Grothendieck's impact can be felt in type theory and logic. For instance, Bart Jacobs' 700+ page volume <em><a href="http://www.cs.ru.nl/B.Jacobs/CLT/bookinfo.html">Categorical Logic and Type Theory</a></em> 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 <a href="http://ncatlab.org/nlab/show/Grothendieck+fibration">Grothendieck fibrations</a> (also called a cartesian fibrations). Similarly,
the notion of <a href="http://en.wikipedia.org/wiki/Topos">Topos</a>, 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. </p>

CC BY-SA 3.0
2014-11-17T23:34:50.707Z
$\subseteq$ over $\in$ because it comes first in setting up an elementary topos?
Nikolaj-K
CC BY-SA 3.0
2014-11-18T08:38:48.470Z
@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.
Dave Clarke
CC BY-SA 3.0
2014-11-16T11:48:04.660Z
2014-11-16T16:00:00.077Z
2014-11-16T16:00:00.077Z
Dave Clarke
<p>Any applications of $p$-adic cohomology, etale cohomology in point counting formulas for algebraic varieties has roots in his work.</p>

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

CC BY-SA 3.0
2014-11-16T21:19:32.050Z
Are these applications in theoretical computer science? It all sounds like mathematics to me – or probably that other bit of TCS.
Dave Clarke
CC BY-SA 3.0
2014-11-16T21:22:14.107Z
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.
Turbo
CC BY-SA 3.0
2014-11-16T21:06:37.220Z
2014-11-16T21:06:37.220Z
Turbo
<p><a href="http://en.wikipedia.org/wiki/Grothendieck_inequality">Grothendieck's inequality</a>, 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 <em>after</em> the paper was published. Pisier gives a very detailed account of the inequality, its variants, and its tremendous influence on functional analysis in his <a href="http://www.math.tamu.edu/~pisier/grothendieck.pdf">survey</a>. </p>

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

<p>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 <a href="http://arxiv.org/abs/1108.2464">survey</a> its multiple applications and connections to combinatorial optimization. </p>

<p>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 <a href="http://www.cs.huji.ac.il/~nati/PAPERS/ccfn.pdf">Linial and Shraibman</a> in work on communication complexity, and even turned out useful in work on <a href="http://arxiv.org/abs/1308.1385">private data analysis</a> (shameless plug). </p>

CC BY-SA 3.0
2014-11-14T20:44:28.020Z
[Here](https://plus.google.com/114134834346472219368/posts/NqTkJb6Ns6m) is another text on [Grothendieck's inequality](http://en.wikipedia.org/wiki/Grothendieck_inequality) and CS. But I am not qualified to comment.
babou
CC BY-SA 3.0
2014-11-14T21:37:20.483Z
A lecture by Giles Pisier at IHES might also be interesting: http://www.dailymotion.com/video/x8jes6_colloque-grothendieck-gilles-pisier_tech (unfortunately it's interrupted by annoying ads).
Sasho Nikolov
CC BY-SA 3.0
2014-11-14T20:33:28.650Z
2014-11-14T20:33:28.650Z
Sasho Nikolov
<p><a href="http://www.liberation.fr/sciences/2014/11/13/alexandre-grothendieck-ou-la-mort-d-un-genie-qui-voulait-se-faire-oublier_1142614?xtor=rss-450" rel="nofollow noreferrer">Grothendieck has passed away</a>. 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 <a href="https://cstheory.stackexchange.com/questions/11797/alan-turings-contributions-to-computer-science">Alan Turing&#39;s Contributions to Computer Science</a>.</p>

<blockquote>
  <p>What are <a href="http://en.wikipedia.org/wiki/Alexander_Grothendieck" rel="nofollow noreferrer">Grothendieck</a>'s major influences on theoretical computer science?</p>
</blockquote>

CC BY-SA 3.0
2014-11-14T19:04:46.843Z
[obituary in English](http://abcnews.go.com/Technology/wireStory/mathematics-great-grothendieck-86-dies-france-26910211) / ABCNews
vzn
CC BY-SA 3.0
2014-11-14T20:28:29.620Z
Maybe this is relevant: [Is Grothendieck a computer?](http://mathoverflow.net/questions/48864/is-grothendieck-a-computer)
babou
CC BY-SA 3.0
2014-11-14T20:41:08.400Z
I hope someone from theory B writes about category theory and Grothendieck topologies (or is his work there not relevant to computer science?).
Sasho Nikolov
CC BY-SA 3.0
2014-11-14T21:22:57.260Z
fyi some sketch/ outline of an answer from [reddit](http://www.reddit.com/r/math/comments/2m82zw/reports_are_coming_in_of_the_death_of_alexandre/cm2m45t) / "frobenius"
vzn
CC BY-SA 3.0
2014-11-16T09:15:28.803Z
@SashoNikolov: I've seen his name pop up from time to time in Theory B papers, but I don't feel qualified to tell a good story about it.
Dave Clarke
CC BY-SA 3.0
2014-11-16T09:29:06.570Z
Maybe @AndrejBauer can help.
Sasho Nikolov
CC BY-SA 3.0
2014-11-17T11:00:48.747Z
KW Regan wrote [something on Lipton's blog](http://rjlipton.wordpress.com/2014/11/16/alexander-grothendieck-1928-2014/).
Raphael
<big-picture><ct.category-theory><ho.history-overview>
Impact of Grothendieck's program on TCS
vzn
# Impact of Grothendieck's program on TCS

(Asked by: username_0 on 2014-11-14)

[Grothendieck has passed away](http://www.liberation.fr/sciences/2014/11/13/alexandre-grothendieck-ou-la-mort-d-un-genie-qui-voulait-se-faire-oublier_1142614?xtor=rss-450). 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](https://cstheory.stackexchange.com/questions/11797/alan-turings-contributions-to-computer-science).

> What are [Grothendieck](http://en.wikipedia.org/wiki/Alexander_Grothendieck)'s major influences on theoretical computer science?

**Tags:** big-picture, ct.category-theory, ho.history-overview

> **Comments:**
> **username_0**: [obituary in English](http://abcnews.go.com/Technology/wireStory/mathematics-great-grothendieck-86-dies-france-26910211) / ABCNews  
> **username_1**: Maybe this is relevant: [Is Grothendieck a computer?](http://mathoverflow.net/questions/48864/is-grothendieck-a-computer)  
> **username_2**: I hope someone from theory B writes about category theory and Grothendieck topologies (or is his work there not relevant to computer science?).  
> **username_0**: fyi some sketch/ outline of an answer from [reddit](http://www.reddit.com/r/math/comments/2m82zw/reports_are_coming_in_of_the_death_of_alexandre/cm2m45t) / "frobenius"  
> **username_3**: @SashoNikolov: I've seen his name pop up from time to time in Theory B papers, but I don't feel qualified to tell a good story about it.  
> **username_2**: Maybe @AndrejBauer can help.  
> **username_4**: KW Regan wrote [something on Lipton's blog](http://rjlipton.wordpress.com/2014/11/16/alexander-grothendieck-1928-2014/).  

---

## 3 answers

### Answer by username_2 on 2014-11-14. Score: 29 | Accepted answer

[Grothendieck's inequality](http://en.wikipedia.org/wiki/Grothendieck_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](http://www.math.tamu.edu/~pisier/grothendieck.pdf).

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](http://arxiv.org/abs/1108.2464) 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](http://www.cs.huji.ac.il/~nati/PAPERS/ccfn.pdf) in work on communication complexity, and even turned out useful in work on [private data analysis](http://arxiv.org/abs/1308.1385) (shameless plug).

> **Comments:**
> **username_1**: [Here](https://plus.google.com/114134834346472219368/posts/NqTkJb6Ns6m) is another text on [Grothendieck's inequality](http://en.wikipedia.org/wiki/Grothendieck_inequality) and CS. But I am not qualified to comment.  
> **username_2**: A lecture by Giles Pisier at IHES might also be interesting: http://www.dailymotion.com/video/x8jes6_colloque-grothendieck-gilles-pisier_tech (unfortunately it's interrupted by annoying ads).  

---

### Answer by username_3 on 2014-11-16. Score: 20

Grothendieck's impact can be felt in type theory and logic. For instance, Bart Jacobs' 700+ page volume *[Categorical Logic and Type Theory](http://www.cs.ru.nl/B.Jacobs/CLT/bookinfo.html)* 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](http://ncatlab.org/nlab/show/Grothendieck+fibration) (also called a cartesian fibrations). Similarly,
the notion of [Topos](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_5**: $\subseteq$ over $\in$ because it comes first in setting up an elementary topos?  
> **username_3**: @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.  

---

### Answer by username_6 on 2014-11-16. Score: 13

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.

> **Comments:**
> **username_3**: Are these applications in theoretical computer science? It all sounds like mathematics to me – or probably that other bit of TCS.  
> **username_6**: 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.  

---

