6.895 Randomness and Computation (H)

L MW2:30-4, Room 36-112
Professor Ronitt Rubinfeld, ronitt@csail.mit.edu, 32-G698
Prereq.: 6.046J, 6.840J
3-0-9

This subject qualifies as a Theoretical Computer Science Engineering Concentration subject.

The power and sources of randomness in computation. Topics include:

(1) Basic tools: polynomial zero testing, linearity testing, uniform generation and approximate counting, the influence of variables.

(2) Randomness in various computational settings: computational learning theory,communication complexity, probabilistic proofs.

(3) Generating randomness: pseudorandom generators, derandomization, expanders, extractors.