Es scheint, dass die Theorie der geometrischen Komplexität viel Wissen über reine Mathematik wie algebraische Geometrie und Darstellungstheorie erfordert.
Während ich ein CS-Student bin und KEINEN sehr abstrakten und reinen Mathematikunterricht habe, interessiere ich mich für dieses Programm.
Gibt es eine Liste mit "Mindestkenntnissen" zum Erlernen dieser Theorie?
Diese Liste enthält Vorlesungsunterlagen von CS- oder Mathe-Abteilungen, Umfragen von Zeitschriften oder Konferenzen sowie Lehrbücher für reine Mathematik.
[ BEARBEITEN: Später hinzugefügt ] Vielen Dank für Ihre Kommentare.
Allgemeine Computertheorie: Ich las Sipsers Buch mit dem Titel "Einführung in die Theorie der Berechnung"
Komplexitätstheorie: Insbesondere interessiere ich mich für konkrete Modelle für untere Grenzen der Komplexität. So las ich den Teil der "konkreten Untergrenzen" in Arora-Baraks Lehrbuch. Ich habe auch Grundkenntnisse in den verschiedenen Abschnitten des von Nisan verfassten Buches über Kommunikationskomplexität.
Grundlegende Mathematik: Ich habe etwas über beweisbasierte lineare Algebra wie die allgemeine Definition des Vektorraums usw. und das genaue Argument von Berechnungen gelernt, die auf dem Epsilon-Delta-Argument basieren.
Algebra: Ich habe Definitionen und Beispiele von Gruppen, Ringen und Feldern gelernt. Ich hatte eine Klasse für Cs-Studenten und habe nichts über die allgemeinen Kenntnisse dieses algebraischen Systems gelernt.
quelle
Antworten:
Die kurze Antwort : Das wirklich minimale mathematische Wissen, um die erste Hälfte des Plans von GCT zu verstehen, wenn Sie ein wenig von Gruppen, Ringen und Feldern gesehen haben, ist im Grunde in Kapitel 3 meiner These (Schamloser Selbstpfropfen) beschrieben ). Dieses Kapitel ist jedoch unvollständig, da ich nicht auf die Darstellungstheorie eingehen kann. Die Darstellungstheorie ist entscheidend für die zweite Hälfte des Plans (weshalb ich daran arbeite, dieses Kapitel zu erweitern).
Wenn Sie sich wirklich mit GCT, Symmetrie, Darstellungen und Invarianten von Goodman und Wallach und Aktionen und Invarianten algebraischer Gruppen von W. Ferrers Santos befassen möchten, sind beide relativ eigenständig und verfügen über viele gute Informationen, die für GCT relevant sind. Ich bin nicht sicher, ob sie die besten Quellen sind, aus denen ich lernen kann, da ich sie erst kennengelernt habe, nachdem ich viel von diesem Material gelernt habe, aber sie sind gut in Bezug auf das Verhältnis von dem, was sie abdecken, zu dem, was für GCT relevant ist. Fulton und Harris eignen sich hervorragend für die Darstellungstheorie, und viele der Beispiele / Übungen in diesem Buch sind für GCT relevant.
Die längere Antwort : Es hängt wirklich davon ab, was bzw. wie viel Sie über GCT lernen möchten, wie Vijay betonte. Die folgenden Themen sind genau das, was meiner Meinung nach als Hintergrund benötigt wird, da dies die Frage war. Ich bin mir nicht sicher, ob dies eine vollständige Liste ist. Ich würde empfehlen, einige Artikel über GCT zu lesen, und wenn Sie sich verlaufen haben, suchen Sie nach Hintergrundmaterial. Während Sie das Hintergrundmaterial lernen, kehren Sie immer wieder zu den GCT-Papieren zurück und versuchen, weitere Informationen zu erhalten.
(Abhängig davon, was Sie lernen möchten, würde ich Zeyu nicht zustimmen, dass Sie zuerst eine kommutative Algebra für Hochschulabsolventen ausprobieren sollten, obwohl dies irgendwann beim Erlernen der GCT erforderlich sein wird.)
Wenn Sie beispielsweise Mulmuleys jüngstes FOCS-Papier verstehen möchten, sollten Sie Folgendes verstehen:
Wenn Sie den allgemeinen Überblick über den GCT-Ansatz verstehen möchten, aber einige mathematische Details haben möchten , würde ich Folgendes vorschlagen:
Das permanente versus determinante Problem. # P-Vollständigkeit der permanenten und GapL-Vollständigkeit der Determinante. Agrawal hat hierzu eine gute Übersicht (nur sehr wenig veraltet), und die Nachweise der Vollständigkeit sind in Burgissers Buch Vollständigkeit und Reduktion der algebraischen Komplexitätstheorie zu finden .
Gruppen und Gruppenaktionen (algebraische Gruppen und algebraische Gruppenaktionen sind hilfreich, aber auf dieser Ebene nicht erforderlich). Sie sollten das Orbit-Stabilizer-Theorem verstehen.
Affine algebraische Geometrie durch Hilberts Nullstellensatz. Grundsätzlich müssen Sie nur die Korrespondenz zwischen affinen algebraischen Varietäten und ihren Koordinatenringen verstehen.
Wenn Sie genau verstehen möchten, was vor sich geht (und ich bin mir nicht sicher, ob ich behaupten kann, hier zu sein, aber ich glaube, ich weiß, was ich wissen muss, um dorthin zu gelangen), sollten Sie wahrscheinlich auch Folgendes verstehen:
Die Struktur reduktiver algebraischer Gruppen und Umlaufbahnabschlüsse in ihren Darstellungen. Ich mag das Buch von W. Ferrers Santos dafür, aber auch Linear Algebraic Groups von Borel , The Classical Groups von Weyl und andere Klassiker.
Die Luna-Vust-Maschinerie (Lunas Slice-Theorem, Luna-Vust-Komplexität)
Tannakianische Dualität (siehe den Artikel von Deligne - Milne ; dies wird eine schwierige Lektüre ohne Hintergrundwissen in Kategorietheorie und affinen algebraischen Gruppen sein). Dies besagt im Wesentlichen, dass "(pro-) affine algebraische Gruppen durch ihre Repräsentation bestimmt werden". Ich glaube nicht, dass Sie das ganze Papier brauchen, sondern vielmehr, wie Sie eine Gruppe aus ihrer Kategorie von Darstellungen wiederherstellen können (Kor. 3.4).
Weitere Darstellungstheorie , insbesondere angewendet auf die Koordinatenringe algebraischer Gruppen und deren Umlaufbahnschließungen. Ich wirklich wie das Buch von Goodman und Wallach für diese, vor allem , weil es im Grunde in sich geschlossene, und es hat genau eine Menge von dem, was Sie GCT verstehen müssen. (Auch viele der Expositorien / Seitenabschnitte und Übungen in Fulton und Harris stimmen mit den GCT überein, insbesondere die über Littlewood-Richardson- und Kronecker-Koeffizienten.)
Wenn Sie tatsächlich an der Darstellungstheorie arbeiten möchten, möchten Sie wahrscheinlich eine algebraischere kombinatorische / kombinatorische Darstellungstheorie verstehen. Ich kenne nicht die richtigen Referenzen dafür, aber sicherlich ist es ein Muss, die Littlewood-Richardson-Regel zu verstehen, und Fultons Buch Young Tableaux ist dafür gut.
Die neuesten Veröffentlichungen auf dieser Seite von Dingen, von denen ich weiß, sind Blasiak , Kumar und Bowman, De Visscher und Orellana .
Abhängig davon, in welche Richtung Sie gehen möchten, möchten Sie möglicherweise auch Quantengruppen untersuchen, obwohl dies nicht unbedingt erforderlich ist (Hinweis: Dies ist kein Sonderfall für Gruppen, sondern eine Verallgemeinerung in eine bestimmte Richtung).
Auf der geometrischeren Seite möchten Sie sich mit Dingen wie Differentialgeometrie für tangentiale und oszillierende Räume, Krümmung, duale Varietäten und dergleichen befassen, die der aufgrund von Mignon bekanntesten Untergrenze für Dauerwelle vs. Det zugrunde liegen --Ressayre und gefolgt von Landsberg - Manivel - Ressayre . ( Mignon - Ressayre kann ohne all diese Dinge verstanden werden, aber Sie können ihren Aufsatz locker als Untersuchung der Krümmung bestimmter Sorten ansehen; für eine weniger lockere Darstellung siehe die Verwendung von Doppelsorten in Landsberg - Manivel - Ressayre . ) (Siehe auch Cai, Chen und Li , wodurch Mignon - Ressayre auf alle merkwürdigen Merkmale ausgedehnt wird.) Siehe auch Landsberg und Kadish .
Wenn Sie sich für den GCT-Ansatz zur Matrixmultiplikation interessieren, dreht sich alles um Tensor-, Border- und Sekantenvarianten. Ich würde vorschlagen, sich die Artikel von Burgisser anzusehen - Ikenmeyer , Landsberg und Ottaviani , Landsberg , Landsbergs Umfrage und Buch . Natürlich wäre es auch gut, das klassische Material zur Matrixmultiplikation (sowohl obere als auch untere Schranke) zu kennen, aber das ist eine ganze separate Dose Würmer.
quelle