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\"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.


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: June 25, 2015
Keywords: Mathematics - Logic,Computer Science - Computational Complexity,Computer Science - Information Theory,Computer Science - Logic in Computer Science


Share

Browsing statistics

This page has been seen 31 times.
This article's PDF has been downloaded 64 times.