Location: Soda 405
Time: Thursdays 2:003:30pm
Logistics: Please join the #sp20pcpip channel on Slack for logistics and announcements!
Files: scribe note repository
Over the past 3 decades, one of the biggest advancements in theoretical computer science has come from how we look at the complexity of a problem: instead of considering the fastest algorithms that find a correct solution, what is the complexity of a procedure that verifies correctness and authenticity of a solution? Does it require multiple rounds of conversation? If so, what are the fewest number of rounds that are necessary? Does this answer change when you incorporate randomness: that is, potentially accept incorrect solutions albeit with small probability? Can this notion be carried out reading extremely minimal sections of the proof? Is it possible to convince someone you have the correct solution without giving away what that solution is? All of these intuitive and interesting questions are explored with rigor in the PCP/IP reading group. We will learn the basics of interactive, zeroknowledge, and probabilistically checkable proofs, as well as their various applications.
Date  Topic  Resources 

Week 1 (2/102/14)  Interactive Proofs (IPs), dIP, Graph NonIsomorphism (GNI), MA/AM presented by Max — Thursday 2:003:30pm in Soda 405 

Week 2 (2/172/21)  Some Nice Containments: \(\mathsf{coNP} \subseteq \mathsf{IP}, \mathsf{IP} = \mathsf{PSPACE}\) 

Week 3 (2/242/28)  ZeroKnowledge Proofs 

Week 4 (3/23/6)  Breather week. Nothing is scheduled this week, in case we need time to catch up/finish previous topics. 

Week 5 (3/93/13)  Set Lower Bounds, GNI, public coins 

Week 6 (3/163/20)  Introduction to PCPs 

Week 7 (3/233/27)  Enjoy spring break! 

Week 8 (3/304/3)  PCP theorem part 1  exp size, LPCP, BLR 

Week 9 (4/64/10)  PCP theorem part 2  assignment testers 

Week 10 (4/134/17)  Breather week. Nothing is scheduled this week, in case we need time to catch up/finish previous topics. 

Week 11 (4/204/24)  Hardness of approximation 

Week 12 (4/275/1)  Special Topic. IOPs, SNARKs, Quantum? Q U A N T U M. If quantum interaction can occur within the proof, can we make our proofs stronger? 

Week 13 (5/45/8)  RRR week. Likely nothing planned, good luck with finals! 