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 |
|---|
