Seminar: November 10, 2008

Ketan Mulmuley, University of Chicago

On P vs NP and Geometric Complexity Theory

This is a joint meeting with the Logic Seminar: the talk begins at 2:30pm and will last for two hours.

This series of two talks on November 10--one in logic seminar and one in theory seminar--will complement a series of three high level colloquium talks on GCT on November 5, 12 and 19 (2.30 p.m.). Geometric complexity theory (GCT) is an approach to the P vs. NP problem via algebraic geometry, representation theory, and the theory of a new class of quantum groups, called nonstandard quantum groups, that arise in this approach. In particular, GCT says that the P vs. NP problem in characteristic zero is intimately linked to the Riemann Hypothesis over finite fields. These complementary talks would elaborate on the basic notion of obstructions in GCT. No background in algebraic geometry, representation theory or quantum groups would be assumed.

References for GCT:

The basic plan of GCT is given in:

GCTflip: "On P vs. NP, Geometric Complexity Theory and the Flip I: high level view".

It has been partially implemented in a series of papers:

GCT1 to GCT11.
GCT1 to 4: Joint with Milind Sohoni
GCT5: Joint with Hari Narayanan

GCTflip, its abstract (GCTabs), and GCT1-8 are available on the speaker's personal home page. GCT8-11 are under preparation.