CS294: Foundations of Probabilistic Proofs (F2020)


Instructor(s): Alessandro Chiesa
Teaching Assistant(s): n/a
Time: Tuesdays and Thursdays 11.00-12:30 (California time)
Location: live via Zoom (see Piazza website for links)
Office Hours: time slots announced in the Piazza website

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.

The course was held online and all recorded lectures are available [here].
Links to each individual lecture and slides are also provided in the syllabus below.


This course requires knowledge of basic algorithms (CS 170) and complexity (CS 172).


Completing the course for credit requires regular attendance/participation (on Piazza or during online lecture), completing occasional homework, scribing (once or twice), and a research project.

Reading and Resources

This course has no required textbook. Each lecture will have specific references. This course is a new revision of a prior course on probabilistic proofs from [Spring 2019].


Available on Piazza.


# Date Topic Reading
1 2020.08.27

Interactive Proofs 1   [intro video] [intro slides]   [video] [slides]

  • 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 2020.09.01

Interactive Proofs 2   [video] [slides]

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

The sumcheck protocol:

3 2020.09.03

Interactive Proofs 3   [video] [slides]

  • 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 2020.09.08

Interactive Proofs 4   [video] [slides]

  • 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:


5 2020.09.10

Interactive Proofs 5   [video] [slides]

  • 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:

6 2020.09.15

Interactive Proofs 6   [video] [slides]

  • 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:

7 2020.09.17

Interactive Proofs 7   [video] [slides]

  • 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:


8 2020.09.22

Probabilistically Checkable Proofs 1   [video] [slides]

  • 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:

9 2020.09.24

Probabilistically Checkable Proofs 2   [video] [slides]

  • 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:

10 2020.09.29

Probabilistically Checkable Proofs 3   [video] [slides]

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




11 2020.10.01

Probabilistically Checkable Proofs 4   [video] [slides]

  • 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


12 2020.10.06

Probabilistically Checkable Proofs 5   [video] [slides]

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



13 2020.10.08

PCPs with Sublinear Verification 1   [video] [slides]


14 2020.10.13

PCPs with Sublinear Verification 2   [video] [slides]

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


15 2020.10.15

Interactive Oracle Proofs 1   [video] [slides]

  • 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:

16 2020.10.20

Interactive Oracle Proofs 2   [video] [slides]

  • 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):

17 2020.10.22

Interactive Oracle Proofs 3   [video] [slides]

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

FRI protocol:

18 2020.10.27

Interactive Oracle Proofs 4   [video] [slides]

  • soundness analysis of the FRI protocol

FRI protocol:

Additional reading:

19 2020.10.29

Interactive Oracle Proofs 5   [video] [slides]

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


20 2020.11.03

Proof Composition 1   [video] [slides]

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


21 2020.11.05

Proof Composition 2   [video] [slides]

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


Additional on O(1)-query tests:

22 2020.11.10

Proof Composition 3   [video] [slides]

  • 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


23 2020.11.12

Parallel Repetition   [video] [slides]

  • 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:

24 2020.11.17

Limitation of PCPs and IOPs   [video] [slides]

  • 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 2020.11.19

Holographic Proofs   [video] [slides]

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


X 2020.11.24

No class (Thanksgiving week).

X 2020.11.26

No class (Thanksgiving week).

26 2020.12.01

Class Project Presentations 1

27 2020.12.03

Class Project Presentations 2

X 2020.12.08

No class (RRR week).

X 2020.12.10

No class (RRR week).