Extracting Randomness

In this post I will describe some recent results in extracting randomness in terms of Kolmogorov complexity since I (and some others) find Kolmogorov complexity more intuitive than entropy. If you would like a background in Kolmogorov complexity, here are some notes from a short course I taught a few years ago. I have not verified that the Kolmogorov results listed below actually follow from the extractor results but it should be straightforward.

Let K(x) be the smallest program generating x. We say a string x is random if K(x)≥|x|. For this post we ignore O(log n) additive factors to avoid various coding issues.

The optimal extractor paper of Lu, Reingold, Vadhan and Wigderson gives us the following. Let n=|x| and K(x)≥k. For all α>0, there is a polynomial-time computable f such that f(x) outputs a polynomial list of strings of length (1-α)k such that most of these strings are random. Using probabilistic constructions of extractors, if one only requires f to be computable, we can set α=0 for k≤n/2.

Barak, Impagliazzo and Wigderson have a new result (mentioned here) on extracting randomness from independent sources. For any constant δ>0, there exists a k polynomial in 1/δ and a polynomial-time computable f such that if we have x₁,…,x_k with

1. |x_i|=n for all i,
2. K(x_i)≥δn for all i, and
3. K(x₁x₂…x_k)=K(x₁)+K(x₂)+…+K(x_k) (the x_i's are independent)

then f(x₁…x_k) is a random string of length n.

Even more recently Barak, Kindler, Shaltiel, Sudakov and Wigderson have even a stronger result in this direction (mentioned here). For any constant δ>0, there exists a ε>0 and a polynomial-time computable f such that if we have x₁,…,x₇ with

1. |x_i|=n for all i,
2. K(x_i)≥δn for all i, and
3. K(x₁x₂…x₇)=K(x₁)+K(x₂)+…+K(x₇) (the x_i's are independent)

then f(x₁…x₇) is a random string of length εn.