Spring 2020 — Probabilistically Checkable Proofs & Interactive Proofs

Location: Soda 405

Time: Thursdays 2:00-3:30pm

Logistics: Please join the #sp20-pcpip 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, zero-knowledge, and probabilistically checkable proofs, as well as their various applications.

Additional Resources

  • Our reading group will mostly be a subset of Prof. Alessandro Chiesa’s fantastic Spring 2019 PCPIP course
    • Full video recordings for the course are available here
  • Prof. Luca Trevisan has a course on PCPs and hardness of approximation here
  • Computational Complexity by Arora and Barak has some good introductions to PCPs and IPs. See the draft, chapters 8, 18, and 19.
  • There was a Simons Fall 2019 bootcamp on Probabilistically Checkable Proofs. The lectures by Justin Thaler, Prahladh Harsha, and Alessandro Chiesa are most relevant.
Date Topic Resources
Week 1 (2/10-2/14)

Interactive Proofs (IPs), dIP, Graph Non-Isomorphism (GNI), MA/AM

presented by Max — Thursday 2:00-3:30pm in Soda 405
Week 2 (2/17-2/21)

Some Nice Containments: \(\mathsf{coNP} \subseteq \mathsf{IP}, \mathsf{IP} = \mathsf{PSPACE}\)
Week 3 (2/24-2/28)

Zero-Knowledge Proofs
Week 4 (3/2-3/6)

Breather week. Nothing is scheduled this week, in case we need time to catch up/finish previous topics.
Week 5 (3/9-3/13)

Set Lower Bounds, GNI, public coins
Week 6 (3/16-3/20)

Introduction to PCPs
Week 7 (3/23-3/27)

Enjoy spring break!
Week 8 (3/30-4/3)

PCP theorem part 1 - exp size, LPCP, BLR
Week 9 (4/6-4/10)

PCP theorem part 2 - assignment testers
Week 10 (4/13-4/17)

Breather week. Nothing is scheduled this week, in case we need time to catch up/finish previous topics.
Week 11 (4/20-4/24)

Hardness of approximation
Week 12 (4/27-5/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/4-5/8)

RRR week. Likely nothing planned, good luck with finals!