27
$\begingroup$

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?

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

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

$\endgroup$
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $\subseteq$ over $\in$ because it comes first in setting up an elementary topos? $\endgroup$ – Nikolaj-K Nov 17 '14 at 23:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Dave Clarke Nov 18 '14 at 8:38
12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Are these applications in theoretical computer science? It all sounds like mathematics to me – or probably that other bit of TCS. $\endgroup$ – Dave Clarke Nov 16 '14 at 21:19
  • 7
    $\begingroup$ 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. $\endgroup$ – Turbo Nov 16 '14 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.