Warunek do nauki GCT

Wydaje się, że Teoria Złożoności Geometrycznej wymaga dużej wiedzy na temat czystej matematyki, takiej jak geometria algebraiczna, teoria reprezentacji.

Chociaż jestem studentem CS i NIE mam zajęć z bardzo abstrakcyjnej i czystej matematyki, interesuje mnie ten program.

Czy istnieje lista „minimalnej wiedzy” do nauki tej teorii?

Ta lista zawiera notatki z wykładów z wydziałów matematyki lub matematyki, ankiety dowolnego czasopisma lub konferencji oraz podręczniki z czystej matematyki.

[ EDYCJA: Dodano później ] Dziękujemy za komentarze.

Ogólna teoria informatyki: czytam książkę Sipsera zatytułowaną „Wprowadzenie do teorii obliczeń”

Teoria złożoności: W szczególności interesują mnie konkretne modele dla niższych granic złożoności. Tak więc przeczytałem fragment „konkretnych dolnych granic” w podręczniku Arory-Baraka. Mam również podstawową wiedzę w kilku księgach książki o złożoności komunikacji napisanej przez Nisana.

Podstawowa matematyka: nauczyłem się o algebrze liniowej opartej na dowodach, takiej jak ogólna definicja przestrzeni wektorowej itp., Oraz precyzyjne argumentowanie rachunków na podstawie argumentu epsilon-delta.

Algebra: Nauczyłem się o definicji i przykładach grupy, pierścienia i pola. Miałem klasę dla studentów cs i nie dowiedziałem się o ogólnej liczbie tych systemów algebraicznych.

Krótka odpowiedź : naprawdę minimalna znajomość matematyki, aby zrozumieć pierwszą połowę planu GCT, kiedy zobaczysz trochę grup, pierścieni i pól, jest zasadniczo przedstawiona w rozdziale 3 mojej pracy magicznej (bezwstydna wtyczka ). Ten rozdział jest jednak niepełny, ponieważ nie przechodzę do teorii reprezentacji części. Teoria reprezentacji jest kluczowa dla drugiej połowy planu (dlatego pracuję nad rozszerzeniem tego rozdziału, aby go uwzględnić).

Jeśli naprawdę chcesz dostać się do GCT, symetrii, reprezentacji i niezmienników Goodmana i Wallacha oraz akcji i niezmienników grup algebraicznych W. Ferrers Santos są zarówno względnie samodzielne i mają wiele dobrych informacji, które dotyczą GCT. Nie jestem pewien, czy są to najlepsze źródła do nauki, ponieważ dowiedziałem się o nich dopiero po tym, jak nauczyłem się dużo z tego materiału, ale są dobre pod względem stosunku tego, co obejmują do tego, co jest istotne dla GCT. Fulton i Harris świetnie nadają się do teorii reprezentacji, a wiele przykładów / ćwiczeń zawartych w książce dotyczy GCT.

Dłuższa odpowiedź : tak naprawdę zależy od tego / czego chcesz dowiedzieć się o GCT, jak zauważył Vijay. Poniższe tematy to tylko to, co myślę, że jest tło potrzebne, gdyż było pytanie. Nie jestem pewien, czy jest to pełna lista - zalecałbym przeczytanie niektórych artykułów na GCT, a kiedy się zgubisz, poszukaj materiału w tle. Gdy uczysz się materiału podstawowego, co jakiś czas wracasz do dokumentów GCT i sprawdzasz, czy możesz pójść dalej.

(W zależności od tego, czego chcesz się nauczyć, tak naprawdę nie zgadzam się z Zeyu, że powinieneś najpierw wypróbować algebrę komutacyjną dla absolwentów, chociaż w pewnym momencie nauki GCT stanie się to konieczne.)

Jeśli chcesz zrozumieć, na przykład, najnowszy artykuł FOCS Mulmuleya , musisz zrozumieć:

• zasada twardości kontra losowości (patrz Impagliazzo - Kabanety , a także być może lista artykułów Billa Gasarcha na temat twardości v losowości )
• podstawowa geometria algebraiczna do Nullstellensatz Hilberta i Lemmy normalizacyjnej Noether. Można je znaleźć w dowolnym podstawowym podręczniku geometrii algebraicznej i prawdopodobnie w większości notatek z wykładów na ten temat.
• trochę klasycznej teorii niezmienniczej (tak naprawdę nie potrzebujesz geoemtrycznej teorii niezmienniczej, schematów i książki Mumford-Fogarty-Kirwan do tego artykułu). Przychodzi mi na myśl książka Sturmfelsa Algorytmy w teorii niezmienników .
• $SL_n$

Jeśli chcesz zrozumieć ogólny zarys podejścia GCT, ale z pewnymi szczegółami matematycznymi , proponuję:

• Problem permanentny a wyznacznik. # P-kompletność stałej i GapL-kompletność wyznacznika. Agrawal ma na ten temat dobrą ankietę (tylko nieznacznie nieaktualną), a dowody kompletności można znaleźć w książce Burgissera „Kompletność i redukcje w teorii algebraicznej złożoności” .

• Grupy i akcje grupowe (grupy algebraiczne i algebraiczne działania grupowe są pomocne, ale na tym poziomie nie są konieczne). Powinieneś zrozumieć twierdzenie o stabilizatorze orbity.

• Affine geometria algebraiczna poprzez Nullstellensatz Hilberta. Zasadniczo wystarczy zrozumieć zgodność między afinicznymi odmianami algebraicznymi i ich pierścieniami współrzędnych.

• $GL_n$$GL_n$

Jeśli chcesz głęboko zrozumieć, co się dzieje (i nie jestem pewien, czy mogę jeszcze twierdzić, że tam jestem, ale myślę, że wiem, co muszę wiedzieć, aby się tam dostać), prawdopodobnie powinieneś także zrozumieć:

• Struktura redukcyjnych grup algebraicznych i zamknięć orbit w ich reprezentacjach. Podoba mi się za to książka W. Ferrers Santos , ale także Linearne grupy algebraiczne Borela , The Classical Groups autorstwa Weyl i inne klasyki.

• Maszyneria Luna-Vust (Twierdzenie o plastrze Luny, złożoność Luna-Vust)

• Dualizm Tannakian (patrz artykuł Deligne - Milne ; będzie to trudna lektura bez znajomości teorii kategorii i afinicznych grup algebraicznych). Mówi to w istocie, że „(pro) afiniczne grupy algebraiczne są określone przez ich reprezentacje”. Nie sądzę, żebyś potrzebował całego artykułu, tak bardzo, jak odzyskać grupę z jej kategorii reprezentacji (Cor. 3.4).

• Więcej teorii reprezentacji , szczególnie w odniesieniu do pierścieni współrzędnych grup algebraicznych i ich zamknięć orbit. I naprawdę jak książki Goodmana i Wallach do tego, zwłaszcza dlatego, że w zasadzie samowystarczalny i ma dużo dokładnie to, co trzeba zrozumieć GCT. (Również wiele sekcji ekspozycyjnych / bocznych i ćwiczeń w Fulton i Harris ma rację dla GCT, szczególnie te dotyczące współczynników Littlewooda-Richardsona i Kroneckera.)

Jeśli chcesz faktycznie pracować nad teorią reprezentacji , prawdopodobnie chcesz zrozumieć więcej algebraicznej kombinatoryki / teorii kombinatorycznej reprezentacji. Naprawdę nie znam wszystkich odpowiednich odniesień do tego, ale z pewnością zrozumienie zasady Littlewooda-Richardsona jest koniecznością, a książka Fultona Young Tableaux jest do tego dobra.

Najnowsze artykuły z tej strony, o których wiem, to Blasiak , Kumar i Bowman, De Visscher i Orellana .

W zależności od kierunku, w którym chcesz pójść, możesz także zajrzeć do grup kwantowych, choć niekoniecznie jest to konieczne (uwaga: nie są to szczególne przypadki grup, ale raczej uogólnienie w określonym kierunku).

Po bardziej geometrycznej stronie rzeczy warto przyjrzeć się geometrii różniczkowej dla przestrzeni stycznych i oscylacyjnych, krzywizny, podwójnych odmian i tym podobnych, które leżą u podstaw najlepiej znanej dolnej granicy permu i det ze względu na Mignona --Ressayre, a następnie Landsberg - Manivel - Ressayre . ( Mignon - Ressayre można zrozumieć bez żadnej z tych rzeczy, ale można postrzegać ich pracę luźno jako badanie krzywizny niektórych odmian; dla mniej luźnego poglądu zobacz zastosowanie podwójnych odmian w Landsberg - Manivel - Ressayre . ) (Zobacz także Cai, Chen i Li , która rozszerza Mignon - Ressayre na wszystkie dziwne cechy). Zobacz także Landsberg i Kadish .

Jeśli interesuje Cię podejście GCT do mnożenia macierzy , dotyczy to rangi tensorowej, rangi granicznej i odmian siecznych. Proponuję zajrzeć do artykułów Burgissera - Ikenmeyer , Landsberg i Ottaviani , Landsberg , ankiety i książki Landsberga . Oczywiście dobrze byłoby też znać klasyczne rzeczy na temat mnożenia macierzy (zarówno górne, jak i dolne granice), ale to całkiem osobna puszka robaków.