Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Extracting Randomness

Expand Messages
  • Lance
    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
    • 0 Attachment
      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.