Plan for course


Green       – Things we believe you saw in previous classes.

Blue         – Things we did.

Orange     - Exercise.

Purple      – Things we will not prove in class.

Grey        - Things we did not do.




*   Interactive Proofs. [G-Lecture, Lecture 11]

*   Definition. Graph Non-Isomorphism.

*   Variants:

*   Error magnitude,

*   Public and private coins, 

*   Two-sided and one-sided versions,

*   Rounds

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


*   Counting.

*   #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:

*   How?

·       Through condensing. [PAP 18.2; K-Lecture, Lecture 13]

·       Through the isolating lemma. [MR 12.4.1]

*   Why?

·       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]


*   Approximate counting.

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

*   DLOG.

*   If Perm is worst-case hard, then Perm can not be even weakly approximated (not the same notion of approximation of before!).

*   Worst to Aver reduction for PSPACE.

*   Limitations of reductions with Black-Box Reconstruction.

*   Hardness Amplification.

*   The hard core lemma: A slightly hard distribution has an extremely hard subset – a min-max proof.

*   Yao’s XOR Lemma

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

*   Hard-core bits.

*   Miscellenous

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

*   Circuits. BPP,MA in P|poly, AM in NP|poly.

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

*   Pseudo classes.

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




*   Zero knowledge.

*   Definitions and variants, rounds, public/private, perfect completeness, honest/dishonest verifier, examples.

*   LargeSet, SmallSet.

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

*   Private=public!

*   Honest=dishonest!

*   Non-interactive SZK.