PCPs and Expander Graphs

  • Irit Dinur | Weizmann

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.

Speaker Details

Irit Dinur received her Ph.D in 2001 from Tel-Aviv University. Following a postdoc at the Institute for Advanced Study, NEC, and at the Miller Institute in Berkeley California she joined the faculty of the Hebrew University in Jerusalem. In 2007 She became an associate professor at the Weizmann Institute. Irit is interested in theoretical computer science, and in combinatorics. In particular she is interested in probabilistically checkable proofs, hardness of approximation, and robustness of computation.

Watch Next