Wpływ programu Grothendiecka na TCS

27

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ą?

vzn
źródło
Może to ma znaczenie: Czy Grothendieck to komputer?
babou
6
Mam nadzieję, że ktoś z teorii B pisze o teorii kategorii i topologiach Grothendiecka (czy też jego praca nie ma związku z informatyką?).
Sasho Nikolov
1
FYI jakiś szkic / Zarys odpowiedź od reddit / "Frobenius"
vzn
2
Może @AndrejBauer może pomóc.
Sasho Nikolov

Odpowiedzi:

28

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{xTAy:x{1,1}m,y{1,1}n}
max{i,jaijui,vj:u1,,um,v1,,vnSn+m1},
Sn+m1Rn+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).

Sasho Nikolov
źródło
1
Oto kolejny tekst na temat nierówności i CS Grothendiecka . Ale nie mam uprawnień do komentowania.
babou
Interesujący może być również wykład Gilesa Pisiera z IHES: dailymotion.com/video/… (niestety przeszkadzają mu irytujące reklamy).
Sasho Nikolov
17

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.XX{simple, dependent, polymorphic, higher-order}

Dave Clarke
źródło
over ponieważ jest to pierwszy element w tworzeniu podstawowego toposu?
Nikolaj-K,
1
@NikolajK Nie ma prawdziwego formalny sens mojego użycia nad - Rozdział 11 adresów książki wyższego rzędu Dependent Type Theory, na przykład.
Dave Clarke
12

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.

T ....
źródło
1
Czy te aplikacje są w informatyce teoretycznej? Dla mnie wszystko brzmi jak matematyka - a może jeszcze trochę TCS.
Dave Clarke
7
Tak. Teoria kryptografii i kodowania konsekwentnie wykorzystuje liczenie punktów i sumy Gaussa. Program Mulmuleya jest jedynym, który jest znany z pokonywania wszystkich znanych przeszkód dla separacji kontra . Prawdopodobnie jest też wiele innych aplikacji. VNPVP
T ....