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

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.