Hermann Weyl Lectures | |

Topic: | The PCP theorem |

Speaker: | Irit Dinur |

Affiliation: | Weizmann Institute of Science |

Date: | Monday, November 18 |

Time/Room: | 2:00pm - 3:00pm/Simonyi Hall 101 |

The PCP theorem says that any mathematical proof can be written in a special "PCP" format such that it can be verified, with arbitrarily high probability, by sampling only a few symbols in the proof. Hence the name, Probabilistically Checkable Proofs (PCPs). Alternatively and equivalently, any system of multivariate polynomial equations can be efficiently converted into another, so that if no input satisfies all equations in the former, no input satisfies even a tiny fraction of the equations in the later. Moreover, each of the new equations will involve only 3 variables.