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

_{1},…,x_{k}with- |x
_{i}|=n for all i, - K(x
_{i})≥δn for all i, and - K(x
_{1}x_{2}…x_{k})=K(x_{1})+K(x_{2})+…+K(x_{k}) (the x_{i}'s are independent)

_{1}…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

_{1},…,x_{7}with- |x
_{i}|=n for all i, - K(x
_{i})≥δn for all i, and - K(x
_{1}x_{2}…x_{7})=K(x_{1})+K(x_{2})+…+K(x_{7}) (the x_{i}'s are independent)

_{1}…x_{7}) is a random string of length εn.

--

Posted by Lance to My Computational Complexity Web Log at 7/21/2004 03:35:00 PM- |x