Time\Location: Monday 16:15 and Wednesday at 18:15, room 009The course will closely follow Salil Vadhan's monograph. 
posted Dec 18, 2012, 2:09 AM by Ariel Gabizon
Monday  we described the NisanWigderson pseudorandom generator. I followed the lectures 23 from the following course of Emanuele Viola 
posted Dec 12, 2012, 9:09 AM by Ariel Gabizon
[
updated Feb 22, 2013, 1:44 AM
]
posted Dec 11, 2012, 3:35 AM by Ariel Gabizon
[
updated Dec 18, 2012, 2:15 AM
]
Monday  we finished discussing the switching Lemma, and discussed a connection between large Fourier coefficients and degrees of restrictions due to Linial Mansour and Nisan. Specifically, we proved Lemmas 35 in their paper. Wedensday  we described Mansour's result on DNFs. We then used this result to show that epsilon biased sets are pseudorandom for DNF. Based on the following paper of De, Etesami, Trevisan and Tulsiani. You can also check out Luca Trevisan's blog post on the subject.

posted Dec 4, 2012, 4:02 AM by Ariel Gabizon
[
updated Dec 5, 2012, 8:48 AM
]
Monday  We described the Kushilevitz Mansour learning Algorithm. I roughly followed the following notes of Luca Trevisan (There are some details missing there) Here is another reference. Wedensday  We described the proof of the Switching Lemma. I used these superb notes of Ryan O'Donnell 
posted Nov 27, 2012, 3:41 PM by Ariel Gabizon
[
updated Dec 3, 2012, 3:16 AM
]
On Monday we finished discussing Reingold's algorithm for ST connectivity. The main things we did: Analysis of the ZigZag product  section 4.3.2.3 in the monograph. and the relation between Spectral expansion and Vertex expansion  Theorem 4.6 On Wednesday we discussed epsbiased sets and the basics of discrete Fourier Analysis. We concluded by showing that epsbiased sets fool width2 ROBPs. There is no reference for this result, but the following paper shows a generalization of it to `read k'width 2 ROBP's 
posted Nov 26, 2012, 3:32 AM by Ariel Gabizon
will be moved back to 18:15 due to request.

posted Nov 26, 2012, 3:32 AM by Ariel Gabizon
We discussed graph operations that will be used in Reingold's Algorithm for undirected connectivity. Squaring, Tensoring and the ZigZag product (which we continue to discuss next class) See Section 4.3.2 in the monograph.

posted Nov 21, 2012, 5:13 AM by Ariel Gabizon
We finished describing the BMY pseudorandom generator, and began describing the randomized algorithm for undirected connectivity according to Section 2.4 in the monograph.

posted Nov 13, 2012, 4:11 AM by Ariel Gabizon
We describe the construction of Blum Micali and Yao of Pseudorandom generators from oneway functions. I am using Lectures 12 and 14 in the following notes of Luca Trevisan.
As a first exercise, please do 1)The exercises in the end of Lecture 12 in these notes. 2) Problems 2.3 and 6.1 in Salil's monograph
Please submit a typed solution 
posted Nov 9, 2012, 3:53 AM by Ariel Gabizon
Note that as discussed, the Tuesday class has been moved to Monday 16:15 
