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.