Kolmogorov extraction and resource-bounded zero-one laws
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.