CSE 5329: Pseudorandomness

Lectures: Thursday 2:20pm – 4:10pm  (Schoenbaum Hall 200)
Lecturer:  Pooya Hatami (Dreese Lab 489, last_name.2@osu.edu)
Office Hours: by appointment

Grading: 60% homework + 40% project

Lecture Notes

References:
1. Pseudorandomness by Salil Vadhan
2. Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan
3. Pseudorandom Generators: A Primer by Oded Goldreich

Course Description:
Randomness is an extremely useful tool in almost all areas of computer science (such as algorithms, cryptography, and distributed computing) and mathematics. Can we derandomize algorithms, that is efficiently turn randomized algorithms into deterministic algorithms? Can we save random bits for tasks that do require randomness? 
Can we get randomness from imperfect sources of randomness that have little entropy? Can we construct mathematical objects such as graphs that share many useful properties to that of a random object? What does it mean for a combinatorial object such as a graph or a set of integers or a Boolean function to be “random-like”? In this course we will discuss answers to several questions of this nature, and along the way discuss constructions of very useful pseudorandom objects such as pseudorandom generators, expander graphs, randomness extractors, and Ramsey graphs.