Degree Type


Date of Award


Degree Name

Master of Science


Computer 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.

Copyright Owner

Fengming Wang



OCLC Number


File Format


File Size

39 pages