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.