EECS 395, 495: Derandomization

Quarter Offered

None ;


COURSE DESCRIPTION: In the past twenty years we have seen great progress in removing the need for random bits based on assumptions of hard languages and in some cases no assumptions at all. This course will discuss pseudorandom generators for low time and memory algorithms, extracting randomness from unknown distributions and constructions of combinatorial structures such as expander graphs with their applications.


PREREQUISITES: Experience with mathematical proofs such as EECS 310. All other background will be given in class.

TEXTBOOK: No required textbook.
All students taking the course for credit will be expected to present a recent research paper to the class.