### DIMACS Theoretical Computer Science Seminar

Title: Kolmogorov Extraction

Speaker: **Fengming Wang**, Rutgers University

Date: Wednesday, February 7, 2007 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We apply recent results on extracting randomness from independent
sources to ``extract'' Kolmogorov complexity. For any $\alpha,
\epsilon > 0$, given a string x with K(x) > \alpha|x|, we show how to use a
constant number of advice bits to efficiently compute another string
y, |y|= \Omega(|x|), with K(y) > (1- \epsilon)|y|. This result holds for
both classical and space-bounded Kolmogorov complexity.