In today's Discrete Lunch, we'll discuss randomness extractors. A randomness extractor is a function which maps the points of a probability space to bit strings in such a way that, for all k, all length k strings are produced with equal probability (i.e., either 0 or 2.) One is then interested in the average length of the strings produced by the extractor.^{-k}We will first prove the easy upper bound on the average length of the strings produced by an extractor: the entropy of the probability space. After that, we'll look at a few constructions of randomness extractors. |

Discrete Lunch >