Topics in Theoretical Computer Science: Probilistically 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 will be devoted to the (algebraic) proof of the basic PCP Theorem and basic relation to approximation problems. We will then move on to more advanced topics, such as hardness amplification, the long-code framework, the Unique-Games Conjecture and its implications, and the 2-to-2 Games Theorem.

Duration: Not defined

Cost: Free

Language: English

Type: Self-Paced