Journal of Symbolic Logic · 2014 · 11 citations · 24 references
ComputingComputer ScienceMathematicsAlgorithmsCryptographyProbability TheoryComputability TheoryCryptographic ComplexityRandomized ComplexityRandomized ComputationRandom Oracle ModelRandomized Complexity Theory
Abstract We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15] (also Problem 5.5.19 in [34]). We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.
24
J. H. van Lint · 2020 · 4.5K citations
Lowness properties and randomness
André Nies · Advances in Mathematics · 2004 · 198 citations
Combinatorial aspects of measure and category
Tomek Bartoszyński · Fundamenta Mathematicae · 1987 · 115 citations · Full text
Every sequence is reducible to a random one
Péter Gács · Information and Control · 1986 · 106 citations