Green – Things we believe you saw in previous classes.
Blue – Things we did.
Purple – Things we will not prove in class.
Grey - Things we did not do.
Interactive Proofs. [G-Lecture, Lecture 11]
Definition. Graph Non-Isomorphism.
Public and private coins,
Two-sided and one-sided versions,
Stability under variances:
Error amplification: A simple parallel repetition argument + Tribes. The AND part appears in [G-Modern, Appendix C.1].
LargeSet is in AM. We use (lossless) dispersers (with large degree). We obtain such graphs using a universal family of hash functions.
Private coins do not help. IP(r) is in AM(r+3). [GS].
Prefect completeness can always be arranged. BPP is in S2. AM is in Ő2 (but not known to be in S2).
MA in AM. Few rounds do not help. AM(r+O(1)) =AM(r). Quote (no proof): AM(O(r))=AM(r).
Quote: IP=PSPACE. Many rounds do help (so we believe). If coNP is in AM, then PH collapses.
AM (and so also graph non-isomorphism!) is in NP|poly.
Quote: Under a hardness assumption: AM ∩ coAM = NP ∩ coNP.
Karp Lipton: If NP is P|poly (or if NP in coNP|poly) than PH collapses to S2.
#P, and #P-completeness. [G-Lecture, Lecture 10; PAP 18.1].
#3SAT is complete under Parsimonious reductions. [G-Lecture, Lecture 10.1,10.2; PAP 18.1].
Valiant: perm is #P complete (but not under Parsimonious reductions). [PAP 18.1]
Reducing to unique solutions:
· Through condensing. [PAP 18.2; K-Lecture, Lecture 13]
· Through the isolating lemma. [MR 12.4.1]
· Finding a perfect matching in a bipartite graph, in parallel (RNC). [MR 12.4]
· NP in RPĹP.
PH is in BPĹP. [K-Lecture, Lecture 13]
Toda’s theorem. PH in P#P [K-Lecture, Lecture 12]
LargeSet, SmallSet and ApproximateSet. All #P functions can be well approximated in PLargeSet and hence in BPP^NP.
Basics about Markov Chains.
Gibbs Samplers, and sampling a random q-col (for a large q).
Approximating the number of q-colorings of a d-regular graph, q>2d2. [Hagg, Chapters 7-9]
Approximating the permanent.
Average case complexity
Worst case to Aver case Reductions.
Worst to Aver reduction for PSPACE.
Limitations of reductions with Black-Box Reconstruction.
The hard core lemma: A slightly hard distribution has an extremely hard subset – a min-max proof.
Partial hardness amplification in NP.
Strong hardness amplification in NP.
“Uniform” Hardness Amplification
Weak OWF imply Strong OWF – A cryptographic Concatenation Lemma.
A uniform concatenation lemma when a sampler is available.
The Goldreich-Levin lemma.
Search to decision reduction.
If some easy distribution is hard for some NP language, then the uniform distribution is hard for some other NP language. OWF vs. OWP.
Non-uniform vs. uniform computation.
Derandomization using non-uniform hardness.
The NW generator.
Trevisan’s construction of extractors from the NW generator.
EXP not in P|poly implies partial derandomization of BPP.
Derandomization of MA,AM under non-uniform hardness.
Derandomization implies non-uniform hardness
EXP=MA iff EXP in P|poly
NEXP=MA iff NEXP in P|poly
Derandomization of Promise-BPP implies a lower bound
Derandomization of Identity testing.
Derandomization on average.
Unconditional Gap theorem for BPP
Unconditional derandomization on average for RP.
The case of NP. Unconditional derandomization on average for Graph Isomorphism.
Unconditional gap theorem for AM.
Definitions and variants, rounds, public/private, perfect completeness, honest/dishonest verifier, examples.
SD,ED Complete problems for HVSZK!
Closure under complement!
Cryptography2: Zero knowledge and the existence of one way functions.
Closure under complement!
If SZK contains NP-complete problems, PH collapses.