Time\Location: Monday 16:15 and Wednesday at 18:15, room 009
The course will closely follow Salil Vadhan's monograph.
Ariel Gabizon >
Pseudorandomess- Fall 2012 (at Jagiellonian)
Monday - we described the Nisan-Wigderson pseudorandom generator.
I followed the lectures 2-3 from the following course of Emanuele Viola
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 3-5 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.
On Monday we finished discussing Reingold's algorithm for ST- connectivity.
The main things we did: Analysis of the Zig-Zag product - section 18.104.22.168 in the monograph.
and the relation between Spectral expansion and Vertex expansion - Theorem 4.6
On Wednesday we discussed eps-biased sets and the basics of discrete Fourier Analysis.
We concluded by showing that eps-biased sets fool width-2 ROBPs.
There is no reference for this result, but the following paper shows a generalization of it
to `read k'-width 2 ROBP's
will be moved back to 18:15 due to request.
We discussed graph operations that will be used in Reingold's Algorithm for undirected connectivity.
Squaring, Tensoring and the Zig-Zag product (which we continue to discuss next class)
See Section 4.3.2 in the monograph.
We finished describing the BMY pseudorandom generator,
and began describing the randomized algorithm for undirected connectivity
according to Section 2.4 in the monograph.
We describe the construction of Blum Micali and Yao of Pseudorandom generators from one-way 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
Note that as discussed, the Tuesday class has been moved to Monday 16:15
1-10 of 10