Spring Semester 2012.
Thursdays 12:30-14:30, Taub 8
The course will closely follow Salil Vadhan's monograph. |

Ariel Gabizon >

### Pseudorandomness

#### Class 12

We described the result of Saks and Zhou that BPL is contained in DSPACE(log^{3/2}n). You can see the same lecture notes of Jin-Yi Cai, lecture 21. Or also, the original paper. |

#### Class 11 - June 14th

We finished describing the result of Nisan that BPL is contained in DTISP(poly(n),log^2 n ). I roughly followed lecture 19 in the following lecture notes of Jin-Yi Cai. We started describing the result of Saks and Zhou that BPL is contained in DSPACE(log^{3/2}n) See lecture 20 in the same notes. |

#### Class 10

We described the INW generator following the description of Arora and Barak in Chapter 21.6 (see link in previous post) We started describing the result of Nisan that BPL is contained in DTISP(poly(n),log^2 n ). You can take a look at lecture 19 in the following lecture notes of Jin-Yi Cai |

#### classes 8-9

We described the explicit construction of expanders according to sections 4.3.2-4.3.3. We described the pseudorandom generator of Nisan and Zuckerman - You can take a look at the paper We used the `recycling Lemma' - you can check it out Lemma 21.32 in Chapter 21 of the book of Arora and Barak |

#### 7th class - 15.5

We finished the proof of Thm 4.22 We proved Thm 4.16, showing that spectral expansion implies vertex expansion. We started going over the expander construction in section 4.3.2 describing squaring and tensoring of graphs. |

#### Ex. 2 - Submit by June 7th

1)Let M be the random walk matrix of an undirected regular graph G ( as defined in section 2.4.2) Prove that a) lambda(G) as defined in 2.50, is the second largest eigenvalue of M b) Let u be the vector (1/N,...,1/N) representing the uniform distribution. Let v be a vector such that <u,v>=0. Prove that <u,vM> =0. 2)Prove that for the spectral norm || || of an N*N matrix (dfn 4.5), we have for matrices A,B ||A+B|| <= ||A|| + ||B||. 3) Use the connection between samplers and extractors (6.24) to show that the sampler of Theorem 4.23 and Corollary 4.41 implies the following: For some constant 0<a<1, an explicit (k=a*n,1/100)-extractor with seed length d=O(log n ) and output length m = Omega(k). 4)Solve Problem 4.8. 5)Solve Problem 4.9. |

#### 6th Class - 10.5

We discussed sampling using spectral expanders. We proved the Decomposition Lemma (4.19) and went through most of the proof of Theorem 4.22 , showing that a random walk on a graph with good spectral expansion is a good sampler. |

#### 5th class - 3.5

We defined samplers (dfn 3.29 - note that in the definition we used the function f is always boolean. This corresponds to what is called a hitting or boolean sampler in the book) We discussed the connections of samplers to extractors (6.24)and the analysis of pairwise independence for sampling (subsection 3.5.4) |

#### 4th class - 23.4

We went over the condenser\expander construction of Guruswami Umans and Vadhan - Thm 5.34 in the book. You can also take a look at the paper |

1-10 of 16