Campuses:

Computational complexity

Friday, April 20, 2007 - 9:00am - 9:50am
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
Subscribe to RSS - Computational complexity