Interactive Proofs 1 [video]
- 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:
Interactive Proofs 2 [video]
- sumcheck protocol
- coNP contained in IP
- arithmetization for UNSAT
- P#P contained in IP
The sumcheck protocol:
Interactive Proofs 3 [video]
- 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:
Interactive Proofs 4 [video]
- 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:
Interactive Proofs 5 [video]
- 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:
Interactive Proofs 6 [video]
- 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
The result presented in class:
A survey:
Additional on implementations of GKR's protocol:
Additional on doubly-efficient interactive proofs:
Interactive Proofs 7 [video]
- 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:
Basic Probabilistic Checking 1 [video]
- definition of a PCP verifier
- the complexity class PCPc,s[r,q]Σ
- simple class inclusions
- from q queries to 2 queries
- statement of PCP Theorem
Video:
New York Times article about the PCP Theorem:
Basic Probabilistic Checking 2 [video]
- 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:
Basic Probabilistic Checking 3 [video]
- compiling any LPCP into a PCP
- self-correction
- linearity testing
- BLR test
- analysis via majority decoding
Main:
Additional:
Video:
Basic Probabilistic Checking 4 [video]
- 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:
Basic Probabilistic Checking 5 [video]
- NP ⊆ PCP[log, polylog] with low-degree testing
- definition of low-degree testing
- univariate polynomials
- d+2 random points (any ε)
- d+2 random evenly-spaced points (ε ~ 1/d2)
- multivariate polynomials
- total degree via random lines (ε ~ 1/d2)
Main:
Additional:
PCPs with Sublinear Verification 1 [video]
- NEXP ⊆ PCP[poly, poly]
- why last lecture's approach fails
- verifier would run in exponential time
- definition of oracle satisfiability (OSAT)
- OSAT is NEXP-complete
- OSAT to zero testing
- zero testing to sumcheck
- why last lecture's approach fails
Main:
PCPs with Sublinear Verification 2 [video]
- NTIME(T) ⊆ PCP[ptime=poly(T), vtime=poly(n,log(T))]
- low-degree extension with H of logarithmic size
- low-degree projection polynomials to obtain bits
- PCP-based delegation of computation
Main:
Hardness of Approximation 1 [video]
- definition of an approximation algorithm
- traditional NP reductions do not preserve performance ratio
- hardness of approximating Independent Set within any constant
Main:
Video:
Hardness of Approximation 2 [video]
- randomness-efficient error reduction
- hardness of approximating Independent Set within a polynomial factor
- equivalence of PCPs and GapCSPs
- hardness of approximating SAT
Main:
Reducing Query Complexity 1 [video]
- proof composition will have two ingredients:
- outer PCP is a robust PCP (RPCP)
- inner PCP is a PCP of proximity (PCPP)
- definition of PCPP
- main tool: local decoding of encoded assignment
- CSAT ∈ PCPP[poly, 1]
- modification of exponential-size PCP
- CSAT ∈ PCPP[log, polylog]
- modification of polynomials-size PCP
Main:
Additional on self-correction:
Reducing Query Complexity 2 [video]
- definition of RPCP
- robustization
- PCP[r,q]Σ ⊆ RΩ(1/q)PCP[r,O(q log|Σ|)]{0,1}
- bundling
- PCP[r,q]{0,1} ⊆ PCP[r+log,O(1)]{0,1}q polylog(n)
- conclusion is polynomial-size RPCPs:
- NP ⊆ RΩ(1)PCP[log,polylog]{0,1}
Robustization:
Additional on O(1)-query tests:
No class (spring break).
No class (spring break).
Reducing Query Complexity 3 [video]
- proof composition
- outer PCP is a robust PCP (RPCP)
- inner PCP is a PCP of proximity (PCPP)
- yields a (regular) PCP
- NP ⊆ PCP[O(log n), O(1)] via proof composition
Main:
Parallel Repetition 1 [video]
- reducing queries at expense of alphabet size:
- PCPc,1-ε[r,q]Σ ⊆ PCPc,1-ε/q[r+log(q),2]Σq
- corollary: ∃ ε and a,b s.t. NP ⊆ PCP1,1-ε[a log(n),2]{0,1}b
- parallel repetition (statement only):
- ∀ s ∃ σ ∀ t, PCPc,s[r,2]Σ ⊆ PCPc,σt[tr,2]Σt
- reduces soundness error at expense of alphabet size
- corollary: ∃ a,b ∀ s, NP ⊆ PCP1,s[a log(n) log(1/s),2]{0,1}b log(1/s)
- sliding scale conjecture:
- statement: ∀ s>1/n, NP ⊆ PCP1,s[O(log(n)),O(1)]{0,1}O(log(1/s))
- why parallel repetition is non-trivial:
- equivalence with 2-prover 1-round games
- Feige's "non-interactive agreement" counterexample
Counterexamples:
Additional on parallel repetition
Towards the sliding scale conjecture:
Parallel Repetition 2 [video]
- Verbitsky's Theorem
- combinatorial lines
- Furstenberg–Katznelson Theorem (statement only)
- value of repeated game is the density of largest line-free set
- why it generalizes to more than two provers/players
Short PCPs
- state of the art (statements only)
- NTIME(T) ⊆ PCP[log T + O(loglog T), polylog(T)]
- ∀ ε>0, CSAT ∈ PCP[log N + O(1/ε), Nε]
Main on parallel repetition:
Additional on explicit bounds for Furstenberg–Katznelson:
Interactive Oracle Proofs 1 [video]
- definition of the IOP model
- IOP[k=poly(n), r=poly(n), q=poly(n)]=NEXP
- 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:
Interactive Oracle Proofs 2 [video]
- circuit satisfiability over the boolean field:
- CSAT(𝔽2) ∈ IOP[k=3,l=O(n),q=O(1)]{0,1}
- circuit satisfiability over large and smooth fields 𝔽:
- CSAT(𝔽) ∈ IOP[k=3,l=O(n),q=O(1)]𝔽
- we will prove a weaker statement:
- CSAT(𝔽) ∈ IOP[k=O(log n),l=O(n),q=O(log n)]𝔽
- from circuit satisfiability to bilinear equations
- from bilinear equations to univariate sumcheck
IOPs for CSAT(𝔽2):
IOPs for CSAT(𝔽):
Interactive Oracle Proofs 3 [video]
- univariate sumcheck
- testing proximity to the Reed--Solomon code
- the main challenges
- the FRI protocol
IOPs for CSAT(𝔽):
FRI protocol:
Interactive Oracle Proofs 4 [video]
- soundness analysis of the FRI protocol
FRI protocol:
Additional reading:
Class Project Presentations 1
Class Project Presentations 2
Class Project Presentations 3
No class.
No class.