Geometric Complexity Theory (GCT)

Friday, April 20, 2007 - 9:00am - 9:50am
EE/CS 3-180
Milind Sohoni (Indian Institute of Technology)
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

This is joint work with Ketan Mulmuley.
MSC Code: