Topics in Theoretical Computer Science: Probabilistically Checkable Proofs

In this course, we will present the theory of Probabilistically Checkable Proofs (PCPs), and prove some fundamental consequences of it as well as more recent advances. More specifically, the first half of the course…

Lectures