3:00 pm Monday, April 28, 2008
Algebra, Number Theory, and Combinatorics Seminar: Pseudorandomness and Randomness Extraction by David Zuckerman (UT Computer Science) in RLM 9.166
Randomization appears extremely useful in algorithm design. For example, there are efficient randomized algorithms to factor polynomials over large fields, but no known fast deterministic algorithms. On the other hand, efficient randomized algorithms for primality testing were known since the 1970's, but only in 2002 did researchers devise an efficient deterministic algorithm. Is randomization truly useful, or does every efficient randomized algorithm have an efficient deterministic counterpart? The field of pseudorandomness was developed to attack this question. In this talk we survey this field, focusing on randomness extractors, which are algorithms to extract high-quality randomness from low-quality random sources. We will highlight connections with combinatorics, algebra, and number theory. Submitted by
|
|