Dana Moshkovitz Institute for Advanced Studies |

One of the greatest achievements of Theoretical Computer Science was to show NP-hardness of *approximation* problems. This required a new, surprising understanding about the power of NP: All NP problems have proofs that can be checked probabilistically by reading only a *constant* number of proof symbols. This Theorem became known as the PCP Theorem (PCP stands for Probabilistically Checkable Proofs). |

4:15pm B17 Upson Hall Thursday, March 11, 2010 Refreshments at 3:45pm in the Upson 4th Floor Atrium |

Computer Science Colloquium Spring 2010 |

www.cs.cornell.edu/events/colloquium |

Hardness of Approximation and Probabalistically Checkable Proofs |