Randomness extraction and asymptotic Hamming distance

DOI10.2168/LMCS-9(3:27)2013MaRDI QIDQ2848372zbMATH OpenFDO

Authors Bjørn Kjos-Hanssen, Cameron E. Freer

Publication date 26 September 2013

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.0821

zbMATH Keywords

Hamming distancealgorithmic randomnessrandomness extraction

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: We obtain a non-implication result in the Medvedev degrees by studying sequences that are close to Martin-L"of random in asymptotic Hamming distance. Our result is that the class of stochastically bi-immune sets is not Medvedev reducible to the class of sets having complex packing dimension 1.

Recommendations

• Mass problems and initial segment complexity
• Constructive dimension and Turing degrees
• Randomness extraction in computability theory
• On partial randomness
• Extracting Kolmogorov complexity with applications to dimension zero-one laws

Cited in

(4)

• KL-randomness and effective dimension under strong reducibility
• Impact of the Hamming weight of the difference of two random variables on the probability of its preservation after addition and subtraction
• Count-Min Sketches for Estimating Password Frequency within Hamming Distance Two
• Extracting randomness within a subset is hard

This page was built for publication: Randomness extraction and asymptotic Hamming distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848372)