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.

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 S_{2}. AM is in Õ_{2} (but not known to be in S_{2}).

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 S_{2.}

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 P^{LargeSet} 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>2d^{2}. [Hagg, Chapters 7-9]

Approximating the permanent.

Average case complexity

Worst case to Aver case Reductions.

DLOG.

If

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.

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.

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.