CSE 290, Seminar on Pseudo-randomness, Fall 2013

Professor Shachar Lovett

Email: slovett@cs.ucsd.edu

Class Times: TH 11:00-12:20, Computer Science Building (EBU3b), room 3109

Pseudo-randomness is a broad area in mathematics and computer science, which aims to understand what exact notions of "randomness" are needed for various applications, and how these can be replaced by deterministic and explicit constructions. Applications in computer science include algorithm de-randomization, efficient data structures, streaming algorithms, metric embeddings and more. We will focus on some of the basic building blocks, with the goal of giving you the necessary tools to further explore more specific applications and more advanced topics.

The material will be based on two surveys: Pairwise independence and derandomization by M. Luby and A. Wigderson, and Expander graphs and their applications by S. Hoori. N. Linial and A. Wigderson, as well as on a few research papers.

The presentations will be given by the students (except for the first class, in which I will give an introduction). If you wish to get credit for the class, you need to present. Unless you have a lot of experience, I highly recommend that you present the lecture to me first, at least a few days before class, in order to get feedback.

Classes:

  1. (9/26/13) Introduction. Shachar Lovett.
  2. (10/3/13) Pairwise independence and efficient dictionaries [Chapter 1 of pairwise independence survey]. Grant Jordan.
  3. (10/10/13) Constructions of pairwise independent variables. [Chapter 2 of pairwise independence survey]. Christopher Tosh (notes).
  4. (10/17/13) K-wise independence and codes. [Lecture notes]. Anup Chenthamarakshan and Jiawei Gao.
  5. (10/24/13) Almost K-wise independent variables, small bias distributions, Vazirani XOR lemma [Naor-Naor,AGHP]. Kaave Hosseini.
  6. (10/31/13) Constructions of small-bias distributions. [Naor-Naor,AGHP]. Mark Saroufim.
  7. (11/7/13) Expanders graphs and their many applications. [Chapter 1 of expander graphs survey]. Akshay Balsubramani and Radheshyam Balasundaram.
  8. (11/14/13) Expansion and eigenvalues. [Chapter 2 of expander graphs survey]. Jiapeng Zhang.
  9. (11/21/13) Random walks on expanders graphs. [Chapter 3 of expander graphs survey]. Semih Yavuz.
  10. (11/28/13) Thanksgiving.
  11. (12/5/13) Pseudo-randomness for small space computations. [Nisan]. Marco Carmosino and Igors Stepanovs.