76 citations · 440 across the 53 of their papers we have counts for
26 papers · 1 filter
Algorithmic randomness for Doob's martingale convergence theorem in continuous time
Bjørn Kjos-Hanssen, Paul Kim Long V. Nguyen, Jason Rute
We study Doob's martingale convergence theorem for computable continuous time martingales on Brownian motion, in the context of algorithmic randomness. A characterization of the cl…
Kolmogorov structure functions for automatic complexity
Bjørn Kjos-Hanssen
For a finite word we define and study the Kolmogorov structure function for nondeterministic automatic complexity. We prove upper bounds on that appear to be quite…
Lattice initial segments of the hyperdegrees
Richard A. Shore, Bjørn Kjos-Hanssen
We affirm a conjecture of Sacks [1972] by showing that every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees, . In fact, we…
Lowness notions, measure and domination
Bjørn Kjos-Hanssen, Joseph S. Miller, Reed Solomon
We show that positive measure domination implies uniform almost everywhere domination and that this proof translates into a proof in the subsystem WWKL (but not in RCA) of…
The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
Denis R. Hirschfeldt, Carl G. Jockusch, Bjørn Kjos-Hanssen +2
We study the reverse mathematics and computability-the\-o\-re\-tic strength of (stable) Ramsey's Theorem for pairs and the related principles COH and DNR. We show that SRT im…
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.
Effective dimension of points visited by Brownian motion
Bjørn Kjos-Hanssen, Anil Nerode
We consider the individual points on a Martin-Löf random path of Brownian motion. We show (1) that Khintchine's law of the iterated logarithm holds at almost all points; and (2) th…
Infinite subsets of random sets of integers
Bjørn Kjos-Hanssen
There is an infinite subset of a Martin-Löf random set of integers that does not compute any Martin-Löf random set of integers. To prove this, we show that each real of positive ef…
Martin-Löf randomness and Galton-Watson processes
David Diamondstone, Bjørn Kjos-Hanssen
The members of Martin-Löf random closed sets under a distribution studied by Barmpalias et al. are exactly the infinite paths through Martin-Löf random Galton--Watson trees with su…
How much randomness is needed for statistics?
Bjørn Kjos-Hanssen, Antoine Taveneaux, Neil Thapen
In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure , a choice needs to be made. One approach is to allow randomn…
Finding paths through narrow and wide trees
Stephen Binns, Bjørn Kjos-Hanssen
We consider two axioms of second-order arithmetic. These axioms assert, in two different ways, that infinite but narrow binary trees always have infinite paths. We show that both a…
The probability distribution as a computational resource for randomness testing
Bjørn Kjos-Hanssen
When testing a set of data for randomness according to a probability distribution that depends on a parameter, access to this parameter can be considered as a computational resourc…
Superhighness
André Nies, Bjørn Kjos-Hanssen
We prove that superhigh sets can be jump traceable, answering a question of Cole and Simpson. On the other hand, we show that such sets cannot be weakly 2-random. We also study the…
Self-embeddings of computable trees
Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman +2
We divide the class of infinite computable trees into three types. For the first and second types, computes a nontrivial self-embedding while for the third type computes…
On a conjecture of Dobrinen and Simpson concerning almost everywhere domination
Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman +1
The notions of almost everywhere (a.e.) domination and its uniform version were introduced and studied in reverse mathematics. This paper studies these notions from a recursion-the…
Comparing DNR and WWKL
Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp +1
In Reverse Mathematics, the axiom system DNR, asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL (weak weak König's Lemma).
Kolmogorov complexity and strong approximation of Brownian motion
Bjørn Kjos-Hanssen, Tamás Szabados
Brownian motion and scaled and interpolated simple random walk can be jointly embedded in a probability space in such a way that almost surely the -step walk is within a uniform…
Low for random reals and positive-measure domination
Bjørn Kjos-Hanssen
The low for random reals are characterized topologically, as well as in terms of domination of Turing functionals on a set of positive measure.
Numberings and randomness
Katie Brodhead, Bjørn Kjos-Hanssen
We prove various results on effective numberings and Friedberg numberings of families related to algorithmic randomness. The family of all Martin-Löf random left-computably enumera…
Finding subsets of positive measure
Bjørn Kjos-Hanssen, Jan Reimann
An important theorem of geometric measure theory (first proved by Besicovitch and Davies for Euclidean space) says that every analytic set of non-zero -dimensional Hausdorff mea…
A strong law of computationally weak subsets
Bjørn Kjos-Hanssen
We show that in the setting of fair-coin measure on the power set of the natural numbers, each sufficiently random set has an infinite subset that computes no random set. That is,…
Local initial segments of the Turing degrees
Bjørn Kjos-Hanssen
Recent results on initial segments of the Turing degrees are presented, and some conjectures about initial segments that have implications for the existence of non-trivial automorp…
The Strength of the Grätzer-Schmidt Theorem
Katie Brodhead, Mushfeq Khan, Bjørn Kjos-Hanssen +3
The Grätzer-Schmidt theorem of lattice theory states that each algebraic lattice is isomorphic to the congruence lattice of an algebra. We study the reverse mathematics of this the…