Type: Seminar

Distribution: World

Expiry: 6 Aug 2010

CalTitle1: Joint Colloquium: Landsberg -- P vs NP

Auth: carberry(.pmstaff;1014.2002)@p723.pc.maths.usyd.edu.au

Prof JM Landsberg (Texas A&M University) Friday 6th August, 2.35-3.25pm, Carslaw 175. P vs NP and the geometry of orbit closures Please note the unusual time. This talk was originally announced as an algebra seminar; instead Prof Landsberg will give an expository version of this talk in the colloquium and speak on another topic in the algebra seminar. We will leave for lunch from level 2 at 1 PM. 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.