Videos

Geometric Complexity Theory (GCT)

Presenter
April 20, 2007
Keywords:
  • Computational complexity
MSC:
  • 03D15
Abstract
We will outline a possible approach to outstanding computational complexity theory (CCT) questions. The approach relies on a faithful mapping of these questions to questions in geometric invariant (GIT) theory and representation theory. We begin with a construction of Valiant and show its connection to the Orbit Closure and Membership problems in GIT. Proofs of non-existence of algorithms translate to the existence of obstructions. This immediately leads to the important notion of stability in invariant theory. For stable points, we show that obstructions are easily constructed. We then outline proofs of the stability of forms such as the determinant and the permanent, which are important in CCT. We next define our notion of partially stable points. We pose our problems as (i) to understand the orbit closure for stable points with distinctive stabilizers, and (ii) extension of these results to partially stable points. We finish with an outline of our current attempts at these teo, and also relate it to the wrok of other researchers. This is joint work with Ketan Mulmuley.