Wpływ programu Grothendiecka na TCS

Grothendieck zmarł . Miał ogromny wpływ na matematykę XX wieku trwającą aż do XXI wieku. To pytanie jest zadawane nieco w stylu / duchu, na przykład w sprawie wkładu Alana Turinga w informatykę .

Jakie główne wpływy Grothendiecka na informatykę teoretyczną?

Nierówność Grothendiecka , od jego dni w analizie funkcjonalnej, początkowo udowodniono, że opiera podstawowe normy na przestrzeniach produktów tensorowych. Grothendieck nazwał nierówność „podstawowym twierdzeniem metrycznej teorii przestrzeni produktów tensorowych” i opublikował ją w znanym już artykule z 1958 r. W języku francuskim w brazylijskim czasopiśmie o ograniczonym nakładzie. Artykuł był w dużej mierze ignorowany przez 15 lat, dopóki nie został ponownie odkryty przez Lindenstraussa i Pelczyńskiego (po tym, jak Grothendieck opuścił analizę funkcjonalną). Dokonali wielu przeformułowań głównych wyników pracy, powiązali ją z badaniami nad absolutnie sumującymi operatorami i normami faktoryzacji oraz zauważyli, że Grothendieck rozwiązał „otwarte” problemy, które pojawiły się poartykuł został opublikowany. W swoim badaniu Pisier bardzo szczegółowo opisuje nierówność, jej warianty i ogromny wpływ na analizę funkcjonalną .

$$\max\{x^TAy: x \in \{-1, 1\}^m, y \in \{-1, 1\}^n\}$$ $$\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}\},$$ $\mathbb{S}^{n+m-1}$$\mathbb{R}^{n+m}$. Dowody nierówności dają „algorytmy zaokrąglania”, aw rzeczywistości losowe zaokrąglanie hiperpłaszczyzny Goemansa-Williamsona wykonuje zadanie (ale daje stałą nieoptymalną). Jednak nierówność Grothendiecka jest interesująca, ponieważ analiza algorytmu zaokrąglania musi być „globalna”, tj. Spojrzeć razem na wszystkie warunki funkcji celu.

Powiedziawszy to, nie powinno dziwić, że nierówność Grothendiecka znalazła drugie (trzecie? Czwarte?) Życie w informatyce. Khot i Naor badają jego liczne zastosowania i powiązania z optymalizacją kombinatoryczną.

Historia się nie kończy. Nierówność jest związana z naruszeniami nierówności Bella w mechanice kwantowej (patrz artykuł Pisiera ), została wykorzystana przez Linial i Shraibmana w pracy nad złożonością komunikacji, a nawet okazała się przydatna w pracy nad analizą danych prywatnych (bezwstydna wtyczka).

Wpływ Grothendiecka można odczuć w teorii typów i logice. Na przykład ponad 700 stronicowa logika i teoria typów Barta Jacobsa zapewnia jednolite traktowanie różnych teorii typów ( teoria typu , gdzie ) w oparciu o kategoryczne pojęcie fibracji Grothendiecka (zwanych również fibracjami kartezjańskimi). Podobnie pojęcie Topos , również ze względu na Grothendiecka, odgrywa dużą rolę w zapewnianiu kategorycznej semantyki logice i teorii typów, co jest interesujące zarówno dla logików, jak i teoretycznych informatyków.$X$$X\subseteq \{ \text{simple},$ $\text{dependent},$ $\text{polymorphic},$ $\text{higher-order}\}$

Wszelkie zastosowania kohomologii adycznej, kohomologii etale w formułach zliczania punktów dla odmian algebraicznych mają swoje korzenie w jego pracy.$p$

Zgaduję, że wizję uogólnienia hipotezy Riemanna przez Mulmuleya na polu skończonym pochodzącym z przypuszczeń Weila można uznać za zadawanie pytań, które pierwotnie miały owocne wyniki z kohomologii etale Grothendiecka.