Wednesday, July 21, 2004

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 x1,…,xk with

  1. |xi|=n for all i,
  2. K(xi)≥δn for all i, and
  3. K(x1x2…xk)=K(x1)+K(x2)+…+K(xk) (the xi's are independent)
then f(x1…xk) 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 x1,…,x7 with

  1. |xi|=n for all i,
  2. K(xi)≥δn for all i, and
  3. K(x1x2…x7)=K(x1)+K(x2)+…+K(x7) (the xi's are independent)
then f(x1…x7) is a random string of length εn.

No comments:

Post a Comment