Author | Conference | Journal | Organization | Year | DOI
Look for results that meet for the following criteria:
Academic
Publications
Extracting information is hard: A Turing degree of non-integral effective Hausdorff dimension
Edit
Extracting information is hard: A Turing degree of non-integral effective Hausdorff dimension   (Citations: 8)
BibTex | RIS | RefWorks Download
We construct a Δ20 infinite binary sequence with effective Hausdorff dimension 1/2 that does not compute a sequence of higher dimension. Introduced by Lutz, effective Hausdorff dimension can be viewed as a measure of the information density of a sequence. In particular, the dimension of A∈2ω is the lim inf of the ratio between the information content and length of initial segments of A. Thus the main result demonstrates that it is not always possible to extract information from a partially random source to produce a sequence that has higher information density.
Journal: Advances in Mathematics - ADVAN MATH , vol. 226, no. 1, pp. 373-384, 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.
    • ...Finally, Miller [9] has answered the original question in the negative by constructing a sequence x with randomness rate 1/2 such that for any Turing reduction f , f( x)does not have randomness rate >1/ 2( or f( x)does not exist)...

    Marius Zimand. Two Sources Are Better than One for Increasing the Kolmogorov Complexi...

    • ...The issue of extraction from one infinite sequence has been first raised by Reimann and Terwijn [18], and after a series of partial results [18,14,3], Miller [13] has given a strong negative answer, by constructing a sequence x with dim(x )=1 /2 such that, for any Turing reduction f ,d im(f (x)) ≤ 1/ 2( orf (x )d oes not exist; dim(x) is the constructive Hausdorff dimension of the sequence x)...

    Marius Zimand. Impossibility of independence amplification in Kolmogorov complexity t...

    • ...Miller [16] and Greenberg and Miller [8] obtained a negative result for randomness extraction: there is a real of effective Hausdorff The Strength of the Besicovitch-Davies Theorem 231...

    Bjørn Kjos-Hanssen, et al. The Strength of the Besicovitch-Davies Theorem

    • ...More precisely, building on the result of Nies and Reimann, they have shown that for all constants c1 and c2, with 0 < c1 < c2 < 1, no single effective transformation is able to raise the dimension from c1 to c2 for all sequences with dimension at least c1. Finally, Miller [Mil08] has fully solved the original question, by constructing a sequence x with dim(x) = 1/2 such that, for any Turing reduction f, dim(f(x)) ≤ 1/2 (or f(x) ...

    Jorge Castro, et al. SIGACT News complexity theory column 32

Order by:

Citations (8)

Share this on | Contribute to Academic