CS459: Foundations of Probabilistic Proofs (F2022)


Instructor(s): Alessandro Chiesa
Teaching Assistant(s): Ziyi Guan
Time: Lectures are on Tuesdays and Wednesdays at 13:00-15:00, and Recitations on Wednesdays at 15:00-16:00
Location: Lectures and Recitations are in INM201
Office Hours: Alessandro: after class on Tuesdays in his office; Ziyi: Thursdays at 16:00-17:00 in INJ114

Course Description

The discovery and study of probabilistic proof systems, such as PCPs and IPs, have had a tremendous impact on theoretical computer science. These proof systems have numerous applications (e.g., to hardness of approximation) but one of their most compelling uses is a direct one: to construct cryptographic protocols that enable super fast verification of long computations. This course will introduce students to the foundations of probabilistic proof systems, covering both classical results as well as modern efficient constructions.


This course requires knowledge of basic algorithms and complexity.


Completing the course for credit requires weekly homeworks and end-of-term project. Class attendance is important.

Reading and Resources

This course has no required textbook. Each lecture will have specific references.




# Date Topic Reading
1 2022.09.20

Interactive Proofs 1   

  • introduction to the course
  • definition of interactive proofs
  • GNI is contained in IP (with private coins)
  • IP is contained in PSPACE

Formulation of interactive proofs:


2 2022.09.21

Interactive Proofs 2

  • sumcheck protocol
  • coNP contained in IP
    • arithmetization for UNSAT
  • P#P contained in IP
    • arithmetization for #SAT

The sumcheck protocol:

3 2022.09.27

Interactive Proofs 3

  • definition of QBF
  • PSPACE is contained in IP
    • TQBF is the starting point
    • arithmetization of formula and quantifiers
    • Shamir's protocol (with Shen's degree reduction)
  • TQBF is PSPACE-complete

Shamir's protocol:


4 2022.09.28

Interactive Proofs 4

  • inefficiency of Shamir's protocol
    • honest prover in Shamir's protocol is 2O(n^2)
    • honest prover in Shen's protocol is 2O(n)
    • T-time S-space machines yield 2O(S log T)-time provers
  • doubly-efficient interactive proofs
    • motivation of delegation of computation
    • theorem statement for log-space uniform circuits
  • low-degree extensions (univariate and multivariate)
  • bare bones protocol for layered circuits
    • one sumcheck per layer

The result presented in class:

A survey:

Additional on implementations of GKR's protocol:

Additional on doubly-efficient interactive proofs:

5 2022.10.04

Interactive Proofs 5

  • IP for GI
  • definition of honest-verifier zero knowledge (HVZK)
  • the IP for GI is HVZK
  • definition of malicious-verifier zero knowledge (ZK)
  • the IP for GI is ZK
  • PZK ⊆ SZK ⊆ CZK
  • towards SZK ⊆ coAM
    • running simulator when x ∉ L
    • IP for GI → IP for GNI (!)

On zero knowledge:


6 2022.10.05

Probabilistically Checkable Proofs 1

  • definition of a PCP verifier
  • the complexity class PCPc,s[r,q]Σ
  • simple class inclusions
  • delegation of computation via PCPs


New York Times article about the PCP Theorem:

7 2022.10.11

Probabilistically Checkable Proofs 2

  • exponential-size PCPs
    • NP ⊆ PCP1,0.5[poly(n),O(1)]{0,1}
    • good query complexity, bad proof length
  • linear PCPs
    • the complexity class LPCPc,s[l,r,q]Σ
    • NP ⊆ LPCP1,0.75[O(n2),O(m+n),4]{0,1}

The exponential-size constant-query PCP is the inner PCP in this paper:

8 2022.10.12

Probabilistically Checkable Proofs 3

  • compiling any LPCP into a PCP
  • self-correction
  • linearity testing
    • BLR test
    • analysis via majority decoding




9 2022.10.18

Probabilistically Checkable Proofs 4

  • NP ⊆ PCP[log, polylog] (up to low-degree testing)
    • start from satisfiability of quadratic equations
    • amplify gap via an error-correcting code
    • arithmetization via Reed--Muller instead of Hadamard
    • reduce to sumcheck problem


10 2022.10.19

Probabilistically Checkable Proofs 5

  • NP ⊆ PCP[log, polylog] with low-degree testing
  • definition of low-degree testing
  • univariate polynomials
  • multivariate polynomials



11 2022.10.25

PCPs with Sublinear Verification 1


12 2022.10.26

PCPs with Sublinear Verification 2

  • NTIME(T) ⊆ PCP[ptime=poly(T), vtime=poly(n,log(T))]
  • PCP-based delegation of computation


13 2022.11.01

Interactive Oracle Proofs 1

  • definition of the IOP model
  • PCP as a special case of IOP
  • IP as a special case of IOP
  • IOP-based delegation of computation

IOP model and its compilation into non-interactive arguments:

14 2022.11.02

Interactive Oracle Proofs 2

  • linear-size IOPs for arithmetic computations
    • R1CS(𝔽) ∈ IOP[k=O(log n),l=O(n),q=O(log n)]𝔽
  • the Reed--Solomon encoding
  • univariate sumcheck

IOPs for R1CS(𝔽):

Aditional on IOPs for CSAT(𝔽2):

15 2022.11.08

Interactive Oracle Proofs 3

  • testing proximity to the Reed--Solomon code
  • the main challenges
  • the FRI protocol

FRI protocol:

16 2022.11.09

Interactive Oracle Proofs 4

  • soundness analysis of the FRI protocol

FRI protocol:

Additional reading:

17 2022.11.15

IOPs with Sublinear Verification

  • automata computations over fields
  • linear-size IOP for automata computations (with succinct verification)
  • machines as time trace + memory trace
  • permutation check


18 2022.11.16

Holographic Proofs

  • sublinear verification for any computation
  • offline/online model
  • from holography to preprocessing
  • holographic PCP for NP
  • holographic IOP for NP


19 2022.11.22

Proof Composition 1

  • definition of robust PCPs/IOPs
  • definition of PCPs/IOPs of proximity
  • proof composition theorem (non-interactive and interactive)


20 2022.11.23

Proof Composition 2

  • definition of robust PCP
  • robustification
  • query bundling
  • construction of a robust PCPs


Additional on O(1)-query tests:

21 2022.11.29

Proof Composition 3

  • definition of PCP of proximity (PCPP)
  • PCPP from local decoder and special PCP
  • exp-size constant-query PCPP for NP
  • poly-size polylog-query PCPP for NP
  • PCP Theorem via proof composition


22 2022.11.30

Limitations 1

  • private coins vs public coins
  • definition of AM[k] and MA[k]
  • GNI is contained in AM[2]
    • reduction to approximate counting
    • approximate counting via pairwise-independent hashing
  • IP[k] is contained in AM[k+2]
    • high-level intuition only

Goldwasser--Sipser transformation:


23 2022.12.06

Limitations 2

  • IPs with bounded communication/randomness
    • complexity classes IP[p,v,r] and AM[p,v,r] (prover bits ≤ p, verifier bits ≤ v, random bits ≤ r)
  • IP[p,v,r] is contained in DTime(2O(p+v+r)poly)
    • compute value of game tree
  • IP[p,v] is contained in BPTime(2O(p+v)poly)
    • approximate value of game tree (sub-sample by random tapes)
    • proof via Chernoff bound and union bound
  • AM[p] is contained in BPTime(2O(p log p)poly)
    • approximate value of game tree (sub-sample by transcript-consistent next messages)
    • refine previous analysis via hybrids
  • IP[p] is contained in BPTime(2O(p log p)poly)NP
    • (sketch) as above but transcript consistency is harder

The results presented in class:

Additional results:

24 2022.12.07

Limitations 3

  • statement of the Parallel Repetition Theorem (exponential decay)
  • statement of the Sliding Scale Conjecture
  • limitations of PCPs wrt to soundness error
  • limitations of IOPs wrt to soundness error


Towards the sliding scale conjecture:

25 2022.12.13

Parallel Repetition

  • reducing queries at expense of alphabet size
  • 2-query PCPs vs 2-player 1-round games
  • Verbitsky's Theorem

Main on parallel repetition:


Additional on explicit bounds for Furstenberg–Katznelson:

26 2022.12.14


  • delegation of computation
  • hardness of approximation


27 2022.12.20

Class Project Presentations 1

28 2022.12.21

Class Project Presentations 2