We apply results on extracting randomness
from independent sources to "extract" Kolmogorov complexity. For any
α, ε > 0, given a string x with
K(x) > α|x|, we show how to use a
constant number of advice bits to efficiently compute another string
y, |y|=Ω(|x|), with
K(y) > (1-ε)|y|. This result holds
for both unbounded and space-bounded Kolmogorov complexity.

We use the extraction procedure for space-bounded complexity to
establish zero-one laws for the strong dimension of complexity classes
within ESPACE. For example, Dim(E | ESPACE) is either 0 or 1.

The extraction procedure for unbounded complexity yields a similar
result for constructive strong dimension: for any sequence S
with Dim(S) > 0, there is a sequence T
≤_{T}S with Dim(T) arbitrarily close to
1.

Proceedings of the 33rd International Colloquium on Automata,
Languages, and Programming (Venice, Italy, July 10-14, 2006),
Lecture Notes in Computer Science 4051, pages 335-345.
Springer-Verlag, 2006.
[DOI link]

Technical Report
TR05-105, Electronic Colloquium on Computational Complexity, 2005.