Author | Conference | Journal | Organization | Year | DOI
Look for results that meet for the following criteria:
Academic
Publications
Extracting Kolmogorov complexity with applications to dimension zero-one laws
Edit
Extracting Kolmogorov complexity with applications to dimension zero-one laws  
BibTex | RIS | RefWorks Download
We apply results on extracting randomness from independent sources to “extract” Kolmogorov complexity. For any α,ϵ>0, given a string x with K(x)>α|x|, we show how to use a constant number of advice bits to efficiently compute another string y, |y|=Ω(|x|), with K(y)>(1-ϵ)|y|. This result holds for both unbounded and space-bounded Kolmogorov complexity.We use the extraction procedure for space-bounded complexity to establish zero-one laws for the strong dimensions of complexity classes within ESPACE. The unbounded extraction procedure yields a zero-one law for the constructive strong dimensions of Turing degrees.
Journal: Information and Computation/information and Control - IANDC , vol. 209, no. 4, pp. 627-636, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Share this on | Contribute to Academic