Cameron E. Freer ; Bjoern Kjos-Hanssen - Randomness extraction and asymptotic Hamming distance

lmcs:889 - Logical Methods in Computer Science, September 25, 2013, Volume 9, Issue 3 - https://doi.org/10.2168/LMCS-9(3:27)2013
Randomness extraction and asymptotic Hamming distanceArticle

Authors: Cameron E. Freer ; Bjoern Kjos-Hanssen

We obtain a non-implication result in the Medvedev degrees by studying sequences that are close to Martin-Löf 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.

https://doi.org/10.2168/LMCS-9(3:27)2013
Source: arXiv.org:1008.0821
Volume: Volume 9, Issue 3
Secondary volumes: Selected Papers of the 9th International Conference on Computability and Complexity in Analysis (CCA 2012)
Published on: September 25, 2013
Imported on: December 12, 2012
Keywords: Mathematics - Logic, Computer Science - Computational Complexity, Computer Science - Information Theory, Computer Science - Logic in Computer Science
Licence: arXiv.org - Non-exclusive license to distribute
Funding:
    Source : OpenAIRE Graph
  • Computability and Probability; Funder: National Science Foundation; Code: 0901020
  • FRG: Collaborative Research: Algorithmic Randomness; Funder: National Science Foundation; Code: 0652669

2 Documents citing this article

Share and export

Consultation statistics

This page has been seen 4277 times.
This article's PDF has been downloaded 560 times.