1 |
2017.01.19 |
Introduction (scribe notes by Pratyush Mishra)
- introduction to the course
- definition of interactive proofs
- sumcheck protocol
- coNP contained in IP
- #P contained in IP (and thus all of PH)
- IP contained in PSPACE
|
Lecture notes:
Formulation of interactive proofs:
The sumcheck protocol:
Additional:
|
2 |
2017.01.24 |
Interactive Proofs 1 (scribe notes by Mariel Supina)
- definition of QBF
- PSPACE is contained in IP
- TQBF is the starting point
- arithmetizing formula and quantifiers
- Shamir's protocol (with Shen's degree reduction)
- TQBF is PSPACE-complete
|
Lecture notes:
Shamir's protocol:
Additional:
|
3 |
2017.01.26 |
Interactive Proofs 2 (scribe notes by Bryan O'Gorman)
- public vs private coins
- GNI is contained in IP (with private coins)
- definition of AM (same as IP but public coins)
- GNI is contained in AM[2]
- reduction to approximate counting
- approximate counting via universal hashing
- IP[k] is contained in AM[k+2]
- achieving perfect completeness in AM
|
Lecture notes:
Goldwasser--Sipser transformation:
Additional:
|
4 |
2017.01.31 |
Interactive Proofs 3 (scribe notes by Peter Manohar)
- interactive proofs with bounded communication/randomness
- prover bits ≤ p
- verifier bits ≤ v
- random bits ≤ r
- IP[p,v,r] and AM[p,v,r]
- IP[p,v,r] is contained in DTime(2O(p+v+r)poly)
- IP[p,v] is contained in BPTime(2O(p+v)poly)
- [GH98, Theorem 2]
- 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)
- [GH98, Theorem 3]
- 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
|
Main:
Additional:
|
5 |
2017.02.02 |
Interactive Proofs 4 (scribe notes by Lynn Chua)
- 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
- bare bones protocol [GKR, Section 3]
- layered arithmetic circuits
- wiring predicates
- one sumcheck per layer
|
Main:
Additional on doubly-efficient interactive proofs:
|
6 |
2017.02.07 |
Interactive Proofs 5 (scribe notes by Patrick Lutz)
- low-degree extensions [GKR, Section 2.3]
- definition
- the equality polynomial
- space-efficient evaluation of LDEs
- implementing the bare bones protocol [GKR, Section 4]
- wiring predicates of s-space uniform circuits have LDEs that are computable in log-space
- doubly-efficient IPs for log-space computations
- combining the above two facts
- corollary for Turing machines [GKR, Corollary 4.8]
|
Main:
Additional on doubly-efficient interactive proofs:
Additional on interactive proofs of proximity:
Additional on implementations of GKR's protocol:
|
7 |
2017.02.09 |
Interactive Proofs 6
- 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 (!)
|
Main:
Additional:
Videos:
|
8 |
2017.02.14 |
Basic Probabilistic Checking 1
- the PCP complexity class PCPc,s[r,q]Σ
- PCPc,s[r,q]Σ ↔ gap of 2r q-ary constraints over Σ
- simple class inclusions
- exponential-size PCP for circuit satisfiability
- NP ⊆ PCP1,0.5[poly(n),O(1)]{0,1}
- good query complexity, bad proof length
|
Lecture notes:
Additional:
New York Times article about the PCP Theorem:
|
9 |
2017.02.16 |
Basic Probabilistic Checking 2 (scribe notes by Aditya Mishra)
- linear PCPs
- the complexity class LPCPc,s[r,q,l]Σ
- last time: NP ⊆ LPCP1,0.75[m,3,(n+1)2]{0,1}
- today: compiling any LPCP into a PCP via linearity test
- testing linearity
- BLR test
- analysis via majority decoding
|
Lecture notes:
Main:
Additional:
New York Times article about ZCash, which uses linear PCPs as part of so-called zkSNARKs:
|
10 |
2017.02.21 |
Basic Probabilistic Checking 3 (scribe notes by Izaak Meckler)
- NP ⊆ PCP[log, polylog] (up to low-degree testing)
- start from satisfiability of degree-3 polynomials
- amplify gap via an error-correcting code such as Reed--Solomon
- arithmetization via Reed--Muller instead of Hadamard
- reduce to sumcheck problem
|
Lecture notes:
Main:
Additional:
|
11 |
2017.02.23 |
Basic Probabilistic Checking 4
- 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)
|
Lecture notes:
Additional:
|
12 |
2017.02.28 |
Basic Probabilistic Checking 5
- 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
|
Lecture notes:
Main:
Additional:
|
13 |
2017.03.02 |
Basic Probabilistic Checking 6
- 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
- consequences of the PCP Theorem
- delegation of computation
- comparison of BFLS91 and GKR08
- key parameters:
- prover running time
- verifier running time
- hardness of approximation
|
Lecture notes:
Main:
Additional:
|
14 |
2017.03.07 |
Reducing Query Complexity 1
- Part I of NP ⊆ PCP[O(log n), O(1)] via proof composition
- definition of robust PCPs
- definition of PCPs of Proximity (PCPPs)
- proof composition
- outer robustness and inner proximity
- plan for the next two lectures
|
Lecture notes:
Main:
Additional:
|
15 |
2017.03.09 |
Reducing Query Complexity 2
- Part II of NP ⊆ PCP[O(log n), O(1)] via proof composition
- 1st proof composition:
- outer: NP ⊆ robust-PCP[log, polylog] (robustization of LDE-PCP)
- inner: NP ⊆ PCPP[log, polylog] (prox variant of LDE-PCP - next lecture)
- result: NP ⊆ PCP[log, polyloglog]
- 2nd proof composition:
- outer: NP ⊆ robust-PCP[log, polyloglog] (robustization of previous step)
- inner: NP ⊆ PCPP[poly(n),O(1)] (prox variant of Had-PCP)
- result: desired claim
- robustization
- 1st step: NP ⊆ PCP[O(log n), O(1)]{0,1}polylog(n) - next lecture
- 2nd step: PCP[r, q] ⊆ O(1/q)-robust-PCP[r,O(q)]
- proximity variant of Had-PCP
- Had-PCP + consistency check
|
Lecture notes on robustization:
Lecture notes on proximity variant of Had-PCP:
|
16 |
2017.03.14 |
Reducing Query Complexity 3
- Part III of NP ⊆ PCP[O(log n), O(1)] via proof composition
- NP ⊆ PCPP[log, polylog] (needed to prove from last lecture)
- LDE-PCP + consistency check
- the consistency check relies on self-correction
- NP ⊆ PCP[O(log n), O(1)]{0,1}polylog(n) (needed to prove from last lecture)
- in general: PCP[r,q]{0,1} ⊆ PCP[r+O(log n), O(1)]{0,1}q polylog(n)
- prover writes LDE of the assignment & restrictions to curves
- verifier checks low-degreeness and does a consistency check
- This concludes the proof that NP ⊆ PCP[O(log n), O(1)]!
|
Additional on O(1)-query tests:
Additional on aggregation:
Additional on self-correction:
|
17 |
2017.03.16 |
Reducing Query Complexity 4
- reducing alphabet size at expense of queries:
- PCPc,s[r,q]Σ ⊆ PCPc,s[r,q log |Σ|]{0,1}
- binary alphabet and two queries and perfect completeness is easy:
- PCP1,s[r,2]{0,1} ⊆ P via reduction to 2SAT
- 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
- sequential repetition:
- ∀ t, PCPc,s[r,q]Σ ⊆ PCPc,st[tr,tq]Σ
- reduces soundness error at expense of queries
- 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
|
Lecture notes:
Additional on 'counterexample':
Additional on parallel repetition
Towards the sliding scale conjecture:
|
18 |
2017.03.21 |
Reducing Query Complexity 5
- 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
- parallel repetition yields 3-query PCPs over binary alphabets
- ∀ δ>0, NP ⊆ PCP1,7/8+δ[O(log n),3]{0,1}
- and the verifier's predicate is the OR of three bits
- yields optimal hardness of approximating MAX-E3-SAT
- [H01, Theorem 6.5]
- ∀ ε,δ>0, NP ⊆ PCP1-ε,1/2+δ[O(log n),3]{0,1}
- and the verifier's predicate is the XOR of three bits
- yields optimal hardness of approximating MAX-E3-LIN-2
- [H01, Theorem 5.4]
- introduction to Fourier analysis of boolean functions [H01, Section 2.4]
- linear functions are an orthonormal basis
- Fourier expansion
- Plancherel's Theorem
- Parseval's Theorem
|
Main on parallel repetition:
Additional on explicit bounds for Furstenberg–Katznelson:
More on Fourier analysis of boolean functions:
Additional on 3-query PCPs:
|
19 |
2017.03.23 |
Reducing Query Complexity 6
- using Fourier analysis of boolean functions:
- linearity testing with 0.5+δ agreement
- dictator testing with c=1-ε and s=0.5+δ with 3LIN predicate
- unique games conjecture (statement only)
- ∀ ε,δ>0, NP ⊆ PCP1-ε,1/2+δ[O(log n),3]{0,1}
- and the verifier's predicate is the OR of three bits
- proof assumes UGC (only for simplicity)
|
Lecture notes:
Main:
Additional:
|
X |
2017.03.28 |
No class (spring break).
|
|
X |
2017.03.30 |
No class (spring break).
|
|
20 |
2017.04.04 |
Reducing Proof Length 1
- the proof length in the LDE-PCP
- recall LDE-PCP from a few lectures ago
- reduction from NEXP to OSAT causes cubic blowup
- reduction from vanishing to sumcheck causes quadratic blowup
- idea: structure computation via "programmable" structured CSPs
- routing networks
- butterfly networks and their reverses
- Beneš networks (butterfly network concatenated with its reverse)
- routing algorithm for Beneš networks
|
On proof length vs query complexity:
On Beneš networks:
Additional on the limits of PCP proof length:
|
21 |
2017.04.06 |
Reducing Proof Length 2
- structuring 3SAT via routing networks
- univariate algebraic CSP (UACSP)
- PCP based on UACSP
- univariate arithmetization
|
Lecture notes:
More on efficient NP reductions (using sorting or routing):
More on short PCPs:
|
22 |
2017.04.11 |
Reducing Proof Length 3
- proximity testing to the Reed--Solomon (RS) code
- why Ω(d) queries are needed with no additional help
- the Polishchuk--Spielman bivariate testing theorem
- PCPPs for RS with linear proof length and square-root query complexity
- attempt 1: pack d points into √dx√d square and extend
- attempt 2: divide P(x) by y-q(x) and look at {(z,q(z))}z
- attempt 3: select q carefully to make {(z,q(z))}z nice
- a verifier with square-root query complexity
|
Lecture notes:
Main:
|
23 |
2017.04.13 |
Reducing Proof Length 4 & Gap Amplification 1
- PCPPs for RS with quasilinear proof length and polylogarithmic query complexity
- making the verifier robust
- composing the tester with itself
- conclusion: NTIME(T) ⊆ PCP[log T + O(loglog T), polylog(T)]
- statement of gap amplification
- implies alternative proof of PCP Theorem
- constraint graphs
- the steps of gap amplification:
- degree reduction
- expanderization
- powering
- alphabet reduction
|
Lecture notes:
Main:
Additional on achieving polylogarithmic verifier for short PCPs:
Additional on linear-size PCPs:
|
24 |
2017.04.18 |
Gap Amplification 2
- alphabet reduction
- robustization
- composition
- back to 2 queries
- expander graphs
- eigenvalues of adjacency matrices
- definition of expander (via 2nd highest eigenvalue)
- edge expansion
- relation spetral gap and edge expansion
- Cheeger's inequality (statement only)
- Buser's inequality (with proof)
- expander mixing lemma
- degree reduction (step 1 of 4 of GA)
- place expander at each vertex
- put equality constraints on edges of expander
- keep old constraints on old edges
|
Lecture notes:
Main:
|
25 |
2017.04.20 |
Gap Amplification 3
- expanderization
- map graph G to expander graph H
- H has size twice that of G
- H has gap at least half that of G
- idea: take union of G with an expander
- powering
- map graph G to new graph H
- alphabet goes from Σ to Σdt
- gap grows multiplicatively in t
- proof sketch
|
Lecture notes:
Main:
|
26 |
2017.04.25 |
Class Project Presentations 1
Pratyush Mishra,
Proofs of proximity for context-free grammars and read-once branching programs
Akshayaram Srinivasan,
Zero-knowledge proofs of proximity
Izaak Meckler,
Games and tilings
Lynn Chua,
Constant rate PCPs with sublinear query complexity
Patrick Lutz,
The connection between the unique games conjecture and SDP integrality gaps
Xingyou Song,
UGC-hardness of constraint satisfaction problems
|
|
27 |
2017.04.27 |
Class Project Presentations 2
Mariel Supina,
Quantum zero-knowledge proofs
Bryan O'Gorman,
QIP and qPCP
Peter Manohar,
Testing linearity against no-signaling provers
Aditya Mishra,
Hardness of approximation for Group-Steiner-Tree
Balachandar Kesavan,
Proof sketch and extension of Raz's 2-player parallel repetition theorem
|
|
X |
2017.05.02 |
No class.
|
|
X |
2017.05.04 |
No class.
|
|