20 citations · 132 across the 38 of their papers we have counts for
Showing 2006Show all
3 papers · 1 filter
cs.CC2006★ 12 cited
Finite-State Dimension and Lossy Decompressors
David Doty, Philippe Moser
This paper examines information-theoretic questions regarding the difficulty of compressing data versus the difficulty of decompressing data and the role that information loss play…
cs.CC2006
Dimension Extractors and Optimal Decompression
David Doty
A *dimension extractor* is an algorithm designed to increase the effective dimension -- i.e., the amount of computational randomness -- of an infinite binary sequence, in order to…
cs.CC2006
Finite-State Dimension and Real Arithmetic
David Doty, Jack H. Lutz, Satyadev Nandakumar
We use entropy rates and Schur concavity to prove that, for every integer k >= 2, every nonzero rational number q, and every real number alpha, the base-k expansions of alpha, q+al…