Course information
- Lectures: Tuesdays and Thursdays 2:55pm-4:10pm, Ives 111
- Instructor: Nick Spooner.
Office hours Wednesdays 2-3pm, Gates 315. (Please notify me 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.
Schedule
| Week # |
Date |
Title |
Readings |
| 1 |
Aug 25/27 |
Introduction to interactive proofs |
|
| 2 |
Sep 1/3 |
Sumcheck: IPs for #P |
|
| 3 |
Sep 8/10 |
IP = PSPACE |
|
| 4 |
Sep 15/17 |
GKR protocol |
|
| 5 |
Sep 22/24 |
Introduction to PCPs, linear PCPs for NP |
|
| 6 |
Sep 29/Oct 1 |
Linearity testing and exponential-size PCPs for NP |
|
| 7 |
Oct 6/8 |
Polynomial-size PCPs for NP |
|
| 8 |
Oct 13 (no class)/15 |
Low-degree testing |
|
| 9 |
Oct 20/22 |
|
|
| 10 |
Oct 27/29 |
|
|
| 11 |
Nov 3/5 |
|
|
| 12 |
Nov 10/12 |
|
|
| 13 |
Nov 17/19 |
|
|
| 14 |
Nov 24/26 (no class) |
|
|
| 15 |
Dec 1/3 (last class) |
|
|
Course policies
- Homework: There will be 2-3 homework assignments, which must be handwritten unless you require an accommodation. Homeworks will be graded for completeness only: making a reasonable attempt at every question will grant you full credit. I always prefer partial or wrong answers to AI-generated answers.
- Grade: The overall grade will be 20% participation, 20% homework, 20% scribe notes, and 40% final report.
- 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.
- Generative AI: Course policies permit the use of AI assistants, with certain caveats.
- Be careful: AI tools often produce incorrect or unsubstantiated claims and plagiarised material. 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.
- The only way to really understand the content of the course is to do the homeworks yourself. Delegating this thinking to AI thoroughly undermines your learning.
- For the final project, we will follow the ACM guidelines. In particular, your report should satisfy that "the resulting Work in its totality is an accurate representation of the authors’ underlying work and novel intellectual contributions and is not primarily the result of the tool’s generative capabilities". You must also include an AI disclosure; misleading or inaccurate disclosures constitute an academic integrity violation.
- Participation: Students are expected to attend every meeting of the class (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.