Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-6032
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorBürgisser, Peter-
dc.contributor.authorHüttenhain, Jesko-
dc.date.accessioned2017-07-26T10:28:34Z-
dc.date.available2017-07-26T10:28:34Z-
dc.date.issued2017-
dc.identifier.urihttp://depositonce.tu-berlin.de/handle/11303/6524-
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-6032-
dc.description.abstractValiant's Conjecture is the algebraic version of P vs. NP and serves as our central motivation. The first part of the thesis starts out by giving an introduction to the underlying theory. In the second chapter, we define a complexity measure for integer polynomials which can be seen as a discretization of the original theory and can be studied combinatorically. A different approach to Valiant's conjecture is the Geometric Complexity Theory programme (GCT for short) which was introduced in 2001 by Mulmuley and Sohoni. Chapter 3 serves as an introduction to GCT: Here, the separation of complexity classes is reduced to the existence of certain integer vectors, which we also call obstructions. The final chapter of the first part shows that certain obstructions are in some sense rare and only recently, it was confirmed that these obstructions are insufficient to prove Valiant's conjecture via GCT. In the second part of the thesis, we study the central geometric object of GCT in more detail and generality: Given the action of a general linear group on a space of homogeneous polynomials by variable substitution, we are interested in the closure of certain orbits, in particular the orbit of the determinant polynomial. Before we study the determinant, we first analyze the case where the orbit closure contains only polynomials that arise by variable substitution, possibly by a non-invertible transformation. A complete classification of this case remains open, but we can answer and pose serveral questions to advance it. In Chapter 7, we introduce techniques to classify the boundary of orbit closures in the general case. We can successfully give a description for the 3×3 determinant polynomial and under one remaining assumption, also for the general binomial. We also determine the stabilizer group of the determinant of a generic traceless matrix and can conclude that the orbit closure of this polynomial is always an irreducible component of the boundary of the orbit closure of the determinant.en
dc.description.abstractDie Vermutung von Valiant ist eine algebraische Version des P vs. NP Problems aus der theoretischen Informatik und unsere zentrale Motivation. Im ersten Teil der Arbeit wird daher zunächst die zugrundeliegende Theorie von Valiant zusammengefasst. Im zweiten Kapitel wird ein Komplexitätsmaß für ganzzahlige Polynome definiert, welches die ursprüngliche Theorie noch stärker diskretisiert und sich rein kombinatorisch untersuchen lässt. Ein anderer Ansatz zur Lösung der Vermutung von Valiant ist die Geometrische Komplexitätstheorie, welche 2001 von Mulmuley und Sohoni ins Leben gerufen wurde: Kapitel 3 der Arbeit liefert eine Einführung. Die Trennung von Komplexitätsklassen wird hier auf die Existenz gewisser ganzzahliger Vektoren mit kombinatorischen Eigenschaften reduziert: Diese Vektoren nennen wir auch Obstruktionen. Im letzten Kapitel des ersten Teils wird gezeigt, dass diese Obstruktionen in einem gewissen Sinne selten sind: Erst kürzlich wurde auch bewiesen, dass diese Obstruktionen tatsächlich nicht ausreichen, um Valiant's Vermutung zu beweisen. Valiant's Conjecture is the algebraic version of P vs. NP and serves as our central motivation. The first part of the thesis begins with an introduction to the underlying theory. Der zweite Teil der Arbeit beschäftigt sich näher und in größerer Allgemeinheit mit dem zentralen Konzept der Geometrischen Komplexitätstheorie: Wir betrachten die Wirkung der allgemeinen linearen Gruppe auf einem Raum homogener Polynome durch Variablensubstitution und studieren den topologischen Abschluss bestimmter Bahnen dieser Wirkung. Zunächst wird der Fall studiert, dass jedes Element in diesem Abschluss durch Variablensubstitution entsteht, möglicherweise mittels einer nicht invertierbaren Transformation. Eine vollständige Klassifikation aller Polynome mit dieser Eigenschaft bleibt offen, obwohl wir einige Fragen im Hinblick darauf beantworten können. Es werden weiterhin Techniken vorgestellt, um den Rand eines Bahnabschlusses auch im Allgemeinen zu klassifizieren. Dies gelingt uns für den Fall der 3×3 Determinante und unter einer verbleibenden Annahme auch für das allgemeine Binom. Wir bestimmen hier auch den Stabilisator der Determinante einer allgemeinen, spurlosen Matrix und können schlussfolgern, dass der Bahnabschluss dieses Polynoms stets eine irreduzible Komponente im Rand des Bahnabschlusses der allgemeinen Determinante ist. Der Determinante gilt hier besondere Aufmerksamkeit aufgrund ihrer wichtigen Rolle in der algebraischen Komplexitätstheorie.de
dc.description.sponsorshipDFG, BU 1371/2-2, Geglättete Analyse von Konditionszahlenen
dc.description.sponsorshipDFG, BU 1371/3-2, Geometrische Komplexitätstheorieen
dc.language.isoenen
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/en
dc.subject.ddc512 Algebrade
dc.subject.ddc516 Geometriede
dc.subject.otheralgebraic geometryen
dc.subject.othercomplexity theoryen
dc.subject.otherrepresentation theoryen
dc.subject.otherclassical groupsen
dc.subject.otherinvariant theoryen
dc.subject.otheralgebraische Geometriede
dc.subject.otherKomplexitätstheoriede
dc.subject.otherDarstellungstheoriede
dc.subject.otherklassische Gruppende
dc.subject.otherInvariantentheoriede
dc.titleGeometric complexity theory and orbit closures of homogeneous formsen
dc.typeDoctoral Thesisen
tub.accessrights.dnbfreeen
tub.publisher.universityorinstitutionTechnische Universität Berlinen
dc.contributor.grantorTechnische Universität Berlinen
dc.contributor.refereeBürgisser, Peter-
dc.contributor.refereeOttaviani, Giorgio-
dc.date.accepted2017-07-03-
dc.title.translatedGeometrische Komplexitätstheorie und Bahnabschlüsse homogener Formende
dc.type.versionacceptedVersionen
Appears in Collections:Inst. Mathematik » Publications

Files in This Item:
File Description SizeFormat 
huettenhain_jesko.pdf1.28 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons