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.