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 distance

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.


    Volume: Volume 9, Issue 3
    Published on: September 25, 2013
    Accepted on: June 25, 2015
    Submitted on: December 12, 2012
    Keywords: Mathematics - Logic,Computer Science - Computational Complexity,Computer Science - Information Theory,Computer Science - Logic in Computer Science
    Fundings :
      Source : OpenAIRE Research Graph
    • Computability and Probability; Funder: National Science Foundation; Code: 0901020
    • FRG: Collaborative Research: Algorithmic Randomness; Funder: National Science Foundation; Code: 0652669

    Linked data

    Source : ScholeXplorer IsReferencedBy DOI 10.1007/s40879-019-00361-4
    • 10.1007/s40879-019-00361-4
    • 10.1007/s40879-019-00361-4
    Extracting randomness within a subset is hard
    Kjos-Hanssen, Bjørn ; Liu, Lu ;

    2 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 1501 times.
    This article's PDF has been downloaded 277 times.