Pseudorandomess- Fall 2012 (at Jagiellonian)

Time\Location: Monday 16:15  and Wednesday at 18:15, room 009
The course will closely follow Salil Vadhan's monograph.

Week 7

posted Dec 18, 2012, 2:09 AM by Ariel Gabizon

Monday - we described the Nisan-Wigderson pseudorandom generator.
I followed the lectures 2-3 from the following course of Emanuele Viola

Ex. 2 - submit by March 15th

posted Dec 12, 2012, 9:09 AM by Ariel Gabizon   [ updated Feb 22, 2013, 1:44 AM ]


Week 6

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 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.

Week 5

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

Week 4

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 Zig-Zag 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 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

Wednesday class

posted Nov 26, 2012, 3:32 AM by Ariel Gabizon

will be moved back to 18:15 due to request.

Class 6-21/11

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 Zig-Zag product (which we continue to discuss next class)
See Section 4.3.2 in the monograph.

Class 5 - 19/11

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.

Second week, 1st Exercise - submit by Dec 2nd

posted Nov 13, 2012, 4:11 AM by Ariel Gabizon

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

Time change

posted Nov 9, 2012, 3:53 AM by Ariel Gabizon

Note that as discussed, the Tuesday class has been moved to Monday 16:15

1-10 of 10