Pseudorandomness

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

Class 12

posted Jun 23, 2012, 9:43 PM by Ariel Gabizon

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

posted Jun 14, 2012, 5:42 AM by Ariel Gabizon

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.

Ex. 3 - Submit by July 10th

posted Jun 10, 2012, 5:02 AM by Ariel Gabizon   [ updated Jun 18, 2012, 10:33 AM ]


Class 10

posted Jun 10, 2012, 5:01 AM by Ariel Gabizon

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

posted May 31, 2012, 8:37 AM by Ariel Gabizon

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

posted May 17, 2012, 8:50 AM by Ariel Gabizon

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

posted May 11, 2012, 12:51 PM by Ariel Gabizon   [ updated Jun 8, 2012, 1:57 PM ]

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

posted May 11, 2012, 11:50 AM by Ariel Gabizon

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

posted May 7, 2012, 7:56 AM by Ariel Gabizon

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

posted Apr 24, 2012, 1:12 AM by Ariel Gabizon

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