Date of Award
Master of Science
Traditional extractors show how to efficiently extract randomness from weak random sources with help of small truly random bits. Recent breakthroughs on multi-source extractors gave an efficient way to extract randomness from independent sources. We apply these techniques to "extract" Kolmogorov complexity. More formally: 1. for any [alpha]> 0, given a string x with K(x)> (x)[superscript a], we show how to use O(log (x)) bits of advice to efficiently compute another string y, (y) = (x)[superscript omega (1)], with K(y)> (y) - O(log (y)); 2. for any [alpha, xi]> 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. We use the above extraction procedure for space-bounded complexity to establish zero-one laws for both polynomial-space strong dimension and strong scaled dimension. Our results include: (i) If Dim[subscript pspace](E)> 0, then Dim[subscript pspace](E/O(l)) = 1. (ii) Dim(E/O(l) l ESPACE) is either 0 or 1. (iii) Dim(E/poly l ESPACE) is either 0 or 1. (iv) Either Dim[superscript (1) over subscript psspace](E/O(n)) = 0 or Dim[superscript ( -1) over subscript pspace(E/0(n)) = 1. In other words, from a dimension standpoint and with respect to a small amount of advice, the exponential-time class E is either minimally complex or maximally complex within ESPACE.
Wang, Fengming, "Kolmogorov extraction and resource-bounded zero-one laws" (2006). Retrospective Theses and Dissertations. 19056.