Abstract
Probabilistically Checkable Proofs (PCPs) provide a format for rewriting proofs of computation such that they can be verified extremely efficiently, in fact by merely probing the (rewritten) proof at a very few (even constant) number of locations. Originally designed for the understanding the limits of approximation algorithms, PCPs have been increasingly used in the context of fast verification. In this tutorial, we will introduce the notion of PCPs and survey some of the ideas that go into the design of efficient PCPs, including topics such as program checking, local testing, arithmetization, and low-degree testing.