P vs NP and the geometry of orbit closures

Abstract:

L. Valiant conjectured an algebraic variant of Cook's conjecture that the complexity classes P and NP are distinct, where one instead compares the determinant and permanent polynomials. K. Mulmuley and M. Sohoni have proposed a program to prove Valiant's conjecture using geometry and representation theory, which they call the Geometric Complexity Theory (GCT) program. I will give an overview of the GCT program, and describe recent work with L. Manivel and N. Ressayre on the program, which led us to solve a classical problem in algebraic geometry regarding dual varieties. Independent of complexity theory, the program has raised many new and beautiful questions regarding the geometry of orbit closures, which I will discuss as time permits.