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

lmcs:889 - Logical Methods in Computer Science, September 25, 2013, Volume 9, Issue 3
Randomness extraction and asymptotic Hamming distance

Authors: Freer, Cameron E. and Kjos-Hanssen, Bjoern

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.

Source : oai:arXiv.org:1008.0821
DOI : 10.2168/LMCS-9(3:27)2013
Volume: Volume 9, Issue 3
Published on: September 25, 2013
Submitted on: December 12, 2012
Keywords: Mathematics - Logic,Computer Science - Computational Complexity,Computer Science - Information Theory,Computer Science - Logic in Computer Science


Export

Share

Consultation statistics

This page has been seen 83 times.
This article's PDF has been downloaded 96 times.