Skip to main content.
Advanced search >
<< Back to previous page Print

<< Thursday, January 31, 2013 >>


Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare


Dissertation Talk: The Computational Complexity of Randomness

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


Thomas Watson, UC Berkeley EECS

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.


tom@cs.berkeley.edu