Title: Randomness Extraction: A Survey
Speaker: David Zuckerman, UT Austin and IAS
Date: Tuesday, April 17, 2012 2:00pm
Location: Hill Center, Room 124, Rutgers University, Busch Campus, Piscataway, NJ
A randomness extractor is an efficient algorithm which extracts high-quality randomness from a low-quality random source. To extract from the most general low-quality sources, a small number of auxiliary high-quality random bits are required. Viewed graph-theoretically, such a seeded extractor has very strong expansion-related properties. Randomness extractors have important applications in a wide variety of areas, including pseudorandomness, cryptography, expander graphs, coding theory, and inapproximability. In this talk, we survey the field of randomness extraction and discuss connections with other areas.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math