76 citations · 207 across the 31 of their papers we have counts for
14 papers · 1 filter
members of thin classes and generic degrees
Frank Stephan, Guohua Wu, Bowen Yuan
A class is thin if every subclass of is the intersection of with some clopen set. In 1993, Cenzer, Downey, Jockusch and Shore initiated the…
On the order dimension of locally countable partial orderings
Kojiro Higuchi, Steffen Lempp, Diip Raghavan +1
We show that the order dimension of the partial order of all finite subsets of under set inclusion is whenever is an infinite cardinal. We also…
Randomness and initial segment complexity for probability measures
Andre Nies, Frank Stephan
We study algorithmic randomness properties for probability measures on Cantor space. We say that a measure on the space of infinite bit sequences is ML absolutely continuous if…
Subrecursive Approximations of Irrational Numbers by Variable Base Sums
Ivan Georgiev, Lars Kristiansen, Frank Stephan
There are numerous ways to represent real numbers. We may use, e.g., Cauchy sequences, Dedekind cuts, numerical base-10 expansions, numerical base-2 expansions and continued fracti…
Equivalences between learning of data and probability distributions, and their applications
George Barmpalias, Nan Fang, Frank Stephan
Algorithmic learning theory traditionally studies the learnability of effective infinite binary sequences (reals), while recent work by [Vitanyi and Chater, 2017] and [Bienvenu et…
Covering the recursive sets
Bjørn Kjos-Hanssen, Frank Stephan, Sebastiaan A. Terwijn
We give solutions to two of the questions in a paper by Brendle, Brooke-Taylor, Ng and Nies. Our examples derive from a 2014 construction by Khan and Miller as well as new direct c…
Closure of resource-bounded randomness notions under polynomial time permutations
Andre Nies, Frank Stephan
An infinite bit sequence is called recursively random if no computable strategy betting along the sequence has unbounded capital. It is well-known that the property of recursive ra…
Higher Kurtz randomness
Bjørn Kjos-Hanssen, André Nies, Frank Stephan +1
A real is -Kurtz random (-Kurtz random) if it is in no closed null set ( set). We show that there is a cone of -Kurtz random hyperdegrees. W…
Lowness for the class of Schnorr random reals
Bjørn Kjos-Hanssen, André Nies, Frank Stephan
We answer a question of Ambos-Spies and Kučera in the affirmative. They asked whether, when a real is low for Schnorr randomness, it is already low for Schnorr tests.
On Martin's Pointed Tree Theorem
Rupert Hölzl, Frank Stephan, Liang Yu
We investigate the reverse mathematics strength of Martin's pointed tree theorem (MPT) and one of its variants, weak Martin's pointed tree theorem (wMPT).
Algorithmic aspects of Lipschitz functions
Cameron Freer, Bjørn Kjos-Hanssen, André Nies +1
We characterize the variation functions of computable Lipschitz functions. We show that a real z is computably random if and only if every computable Lipschitz function is differen…
Anti-complex sets and reducibilities with tiny use
Johanna N. Y. Franklin, Noam Greenberg, Frank Stephan +1
In contrast with the notion of complexity, a set is called anti-complex if the Kolmogorov complexity of the initial segments of chosen by a recursive function is always bou…
Arithmetic complexity via effective names for random sequences
Bjørn Kjos-Hanssen, Frank Stephan, Jason R. Teutsch
We investigate enumerability properties for classes of sets which permit recursive, lexicographically increasing approximations, or left-r.e. sets. In addition to pinpointing the c…
Kolmogorov complexity and the Recursion Theorem
Bjørn Kjos-Hanssen, Wolfgang Merkle, Frank Stephan
Several classes of DNR functions are characterized in terms of Kolmogorov complexity. In particular, a set of natural numbers A can wtt-compute a DNR function iff there is a nontri…