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

Ariel Gabizon >

### Pseudorandomess- Fall 2012 (at Jagiellonian)

#### Week 7

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

#### Week 6

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 4

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 |

#### Class 6-21/11

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

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

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 |

1-10 of 10