Browse Groups

• ## [My Computational Complexity Web Log] Extracting Randomness

(1)
• NextPrevious
• In this post I will describe some recent results in extracting randomness in terms of Kolmogorov complexity since I (and some others) find Kolmogorov
Message 1 of 1 , Jul 21, 2004
View Source
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.

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

Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.