Kolmogorov extraction and resource-bounded zero-one laws

Thumbnail Image
Date
2006-01-01
Authors
Wang, Fengming
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
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.

Comments
Description
Keywords
Citation
DOI
Source
Copyright
Sun Jan 01 00:00:00 UTC 2006