Randomness extraction and asymptotic Hamming distance

DOI10.2168/LMCS-9(3:27)2013zbMATH Open1361.03041arXiv1008.0821MaRDI QIDQ2848372FDOQ2848372

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)

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.

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

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

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)

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)