Topics in Pseudorandomness (Fall 2005-2006)


Exercises: (Exercises are not mandatory. They are meant to give students a chance to practice and make sure that they understand the lectures).


Some Bibliography:

The following is a list if topics covered in class. Whenever possible I give a reference to written matirial on the subject. I use the following method:

Introduction : (Lecture 1). (** Vadhan's lectures 1,2)

Pair-wise and k-wise independence: (Lecture 2) (** Some of this subject is covered in Zuckerman's lecture 5, ** See also a manuscript by Mike Luby and Avi Wigderson. Relevant chapters are: 2,3,4,5, ** See also Vadhan's lecture 7)

Averaging samplers: (Lecture 3) (* A survey on averaging samplers by Oded Goldrecih, ** Vadhan's lecture 2, * Chapters 7,9 in the manuscript of Luby and Wigderson.)

More applications of hashing: (Lecture 4) (** Lectures 5 in a course by Oded Goldreich.)

Small sample spaces: (end of lecture 4, lecture 5 and part of lecture 6) (** Lectures 6,7,8,9 in Zuckerman's notes. Note that this also includes an introduction to error-correcting codes which is our next topic).

Type of tests: eps=0 general eps
k-wise tests k log m k + log log m + log(1/eps)
linear tests m log m + log(1/eps)
poly-size tests m log m + log(1/eps) (existence only. No known explicit construction.)

Error correcting codes: (2nd part of lecture 6 and part of lecture 7). (** Zuckerman's lectures 8,9,10)

Expander graphs: (lecture 8) (*** Vadhan's lecture 9)

Derandomizing BPP: (lectures 9,10)