Course information
- Lectures: Tuesdays and Thursdays 10:10am-11:25am, Gates G13
- Instructor: Nick Spooner.
Office hours Wednesdays 2-3pm, Gates 434. (Please notify in advance if you intend to come to OH.)
Email: nspooner@cornell.edu
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
- Alessandro Chiesa's 2020 Berkeley course covers most of the topics in this class; he provides both video lectures and slides.
- Prashant Vasudevan's 2020 NUS course also covers similar topics; he provides typed notes.
- Justin Thaler's book Proofs, Arguments and Zero Knowledge (available free of charge) is a nice introduction to interactive proofs and their cryptographic applications.
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 |
|
| 6 |
Nov 19/21 |
Linearity testing and exponential-size PCPs for NP |
|
|
Nov 22 (make-up) |
Polynomial-size PCPs for NP |
|
| 7 |
Nov 26 (last class) |
Low-degree testing |
|
Course policies
- Homework: There will be two homework assignments. I strongly prefer that you write your assignments in LaTeX. Assignments are to be submitted directly to the instructor via email.
- Grade: The overall grade will be 20% participation, 40% homework, 40% scribe notes.
- Collaboration and plagiarism: You are free to discuss assignments with your peers, and use internet and textbook resources. However, all submitted work must be your own, and you must acknowledge any resources that you used. In the final report, you must include appropriate citations. Any instance of plagiarism may be subject to investigation according to University regulations.
- AI assistants: Course policies do not forbid the use of AI assistants. However, you should be careful: AI tools often produce incorrect or unsubstantiated claims. The correctness of submitted work remains your responsibility, as does appropriate citation. In particular, is not adequate to cite an AI tool as a source.
- Participation: Students are expected to attend every meeting of the class (though occasional absences will be excused) and participate in discussions.
- Religious observance: As a nonsectarian, inclusive institution, Cornell policy permits members of any religious group to absent themselves from classes without penalty when required for compliance with their religious obligations.
- Disability disclosure: Academic accommodations are available to any student with a chronic, psychological, visual, mobility, learning disability, or who is deaf or hard of hearing.