Geometric complexity theory and orbit closures of homogeneous forms

Valiant'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.

Author dc:creator

• Hüttenhain, Jesko

Advisor dc:contributor.advisor

• Bürgisser, Peter

Licence dc:rights.uri

• https://creativecommons.org/licenses/by-nc-nd/4.0/

Language dc:language.iso

en

Identifier URI

http://dx.doi.org/10.14279/depositonce-6032

OAI identifier oai:identifier

oai:depositonce.tu-berlin.de:11303/6524