Generating Kolmogorov random strings from sources with limited independence
Marius Zimand · Journal of Logic and Computation · 2011
We study whether randomness can be extracted from two strings that are only partially random and only partially independent, where randomness is taken in the sense of Kolmogorov complexity and the dependency of strings x and y is given by dep(x, y) = C(x) + C(y) − C(xy) (C(x) denotes the Kolmogorov complexity of x). The general setting is that the input of the extraction procedure consists of two strings x and y of length n, each having Kolmogorov complexity at least s(n) and dependency at most α(n). It is shown that there exists a computable function that, from two such strings x and y, extracts ≈2s(n) random bits that have Kolmogorov complexity ≈ 2s(n) − α(n) (so the output is α(n) close to being random). It is also shown that (a) it is possible to extract ≈s(n)/2 bits that are α(n) close to being random even conditioned by any one of x or y, and (b) it is possible to construct polynomially many strings of length ≈s(n)/3 that are pairwise α(n) close to being random and also α(n) close to random conditioned by any one of x and y. A polynomial-time extraction procedure exists for the case when x and y have linear Kolmogorov complexity (i.e. C(x) ≥ δn and C(y) ≥ δn, for a constant δ > 0). However, the output is only poly(α(n) + log n) close to random.