Computer Science/Discrete Mathematics Seminar II

The Completeness of the Permanent

In his seminal work, Valiant defined algebraic analogs for the classes P and NP, which are known today as VP and VNP. He also showed that the permanent is VNP-complete (that is, the permanent is in VNP and any problem in VNP is reducible to it). We will describe the ideas behind the proof of this completeness of the permanent.

Date & Time

September 22, 2009 | 10:30am – 12:30pm

Location

S-101

Affiliation

Member, School of Mathematics