COMPUTER SCIENCE/DISCRETE MATH II | |

Topic: | The Completeness of the Permanent |

Speaker: | Amir Yehudayoff |

Affiliation: | Member, School of Mathematics |

Date: | Tuesday, October 6 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Video Link: | https://video.ias.edu/csdm/completenesspermanent |

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.