Dissertation Talk: The Computational Complexity of Randomness

Seminar: Departmental | January 31 | 3-4 p.m. | 606 Soda Hall

Speaker/Performer: Thomas Watson, UC Berkeley EECS

Sponsor: Electrical Engineering and Computer Sciences (EECS)

This talk will cover work on several topics concerning the role of randomness in computational complexity theory. These topics include: (1) Random sampling: the power and limitations of algorithms for producing samples from certain probability distributions. (2) Pseudorandomness: the study of distributions that "look uniform" to every efficient algorithm. (3) Randomness extraction: the process of "refining" crude randomness. (4) Average-case complexity: the study of algorithms that are only guaranteed to work on typical (random) inputs.

Event Contact: tom@cs.berkeley.edu