CS602: Foundations of Probabilistic Proofs (S2022)

Basics

Instructor(s): Alessandro Chiesa
Teaching Assistant(s): Ziyi Guan
Time: Lectures are on Tuesdays and Wednesdays at 11:15-13:00, and Recitations on Fridays at 14:15-15:00
Location: Tuesdays in INM10, Wednesdays in INR219, Fridays in INR219
Office Hours: Alessandro: after class on Wednesdays (in his office), Ziyi: Thursdays 14:00-15: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.

Prerequisites

This course requires knowledge of basic algorithms and complexity.

Requirements

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.

Assignments

TBD.

Schedule

# Date Topic Reading
1 2022.02.22

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:

Video:
2 2022.02.23

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.03.01

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:

Additional:
4 2022.03.02

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.03.08

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:

Video:
6 2022.03.09

Probabilistically Checkable Proofs 1

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

Video:

New York Times article about the PCP Theorem:
7 2022.03.15

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.03.16

Probabilistically Checkable Proofs 3

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

Main:

Additional:

Video:
9 2022.03.22

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

Main:
10 2022.03.23

Probabilistically Checkable Proofs 5

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

Main:

Additional:
11 2022.03.29

PCPs with Sublinear Verification 1

Main:
12 2022.03.30

PCPs with Sublinear Verification 2

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

Main:
13 2022.04.05

Interactive Oracle Proofs 1

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

IOP model and its compilation into non-interactive arguments:
14 2022.04.06

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.04.12

Interactive Oracle Proofs 3

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

FRI protocol:
16 2022.04.13

Interactive Oracle Proofs 4

  • soundness analysis of the FRI protocol

FRI protocol:

Additional reading:
X 2022.04.19

No class (on break).
X 2022.04.20

No class (on break).
17 2022.04.26

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

Main:
18 2022.04.27

Holographic Proofs

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

Main:
19 2022.05.03

Proof Composition 1

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

Main:
20 2022.05.04

Proof Composition 2

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

Robustification:

Additional on O(1)-query tests:
21 2022.05.10

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

Main:
22 2022.05.11

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:

Additional:
23 2022.05.17

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.05.18

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

Main:

Towards the sliding scale conjecture:
25 2022.05.24

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:

Counterexamples:

Additional on explicit bounds for Furstenberg–Katznelson:
26 2022.05.25

Applications

  • delegation of computation
  • hardness of approximation

Reading:
27 2022.05.31

Class Project Presentations 1
28 2022.06.01

Class Project Presentations 2