Mathematical Conversations

The PCP Theorem states that any mathematical proof can be encoded in a way that allows verifying it probabilistically while reading only a small number of bits of the (new) proof. This result has several applications in Theoretical Computer Science, most notably in hardness of approximation problems.

We will discuss this result and some of its consequences. If time permits, we will discuss some of the math that goes into the proof of PCP-type results.