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.

## No comments:

## Post a Comment