PCPs and Expander Graphs

Speaker  Irit Dinur

Host  Yael Kalai and Madhu Sudan

Affiliation  Weizmann

Duration  01:26:36

Date recorded  30 November 2011

A probabilistically checkable proof (PCP) is a special format for writing proofs that is very robust. In this format, a proof of a false theorem is guaranteed to have so many bugs that it can be checked by reading a constant number of random proof bits. The celebrated PCP theorem says that every NP language has a robust "PCP" proof. In the talk we will explain how to construct a PCP by taking any standard NP proof and then routing it through an expander graph (i.e., a graph that is very well-connected). We will also describe a complementary result that shows how in some restricted sense, every construction of a PCP must be based on an expander. No prior knowledge will be assumed. Based in part on joint work with Tali Kaufman.

©2011 Microsoft Corporation. All rights reserved.
> PCPs and Expander Graphs