Course information
Overview
This course offers a graduate-level introduction to the theory of probabilistic proof systems. The area has deep connections to many aspects of theoretical computer science, including complexity theory and hardness of approximation, coding theory, cryptography and quantum computing. Topics covered will include the PCP theorem, interactive proofs, and zero knowledge.
Resources
Homework
Schedule
Week # Date Title Readings
1 Oct 17 Introduction to interactive proofs
2 Oct 22/24 Sumcheck: IPs for #P
3 Oct 29/31 IP = PSPACE
4 Nov 5/7 GKR protocol
5 Nov 12/14 Introduction to PCPs, linear PCPs for NP
Course policies