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.

    https://doi.org/10.2168/LMCS-9(3:27)2013
    Source : oai:arXiv.org:1008.0821
    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
    Licence: arXiv.org - Non-exclusive license to distribute
    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

    Export

    BibTeX TEI DC OpenAIRE Crossref DOAJ zbJATS JSON

    Share

    Consultation statistics

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