PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Stephen Simpson.

Title:Extracting randomness is hard
Seminar:Department of Mathematics Colloquium
Speaker:Joseph S. Miller, University of Wisconsin
Abstract:
Can randomness---or more technically, "information"---be effectively extracted from a semi-random source? A special case of this question was answered by von Neumann in 1951. He described a simple method for extracting an unbiased random sequence from the flips of a biased coin. A more general form of the question was asked by Reimann and Terwijn in the context of algorithmic randomness using effective (Hausdorff) dimension, which measures the information density of an infinite binary sequence. They asked if there is a sequence that has effective Hausdorff dimension 1/2---in other words, a half-random sequence---from which one cannot compute a sequence of higher effective dimension? As it turns out, such sequences exist. After giving an introduction to Kolmogorov complexity and effective Hausdorff dimension, we will discuss this and related results. No previous knowledge will be assumed.

Room Reservation Information

Room Number:MB114
Date:04 / 01 / 2010
Time:04:00pm - 05:00pm