# Category Archives: publications

# Covering the computable sets

I participated in the workshop on Algorithmic Randomness in Singapore and the conference on Computability, Complexity and Randomness.

With host Frank Stephan and fellow participant Sebastiaan Terwijn we wrote a paper entitled Covering the recursive sets which appeared in Lecture Notes in Computer Science, Conference on Computability in Europe, 2015, and has now been published in Annals of Pure and Applied Logic.

# Automatic Complexity Guessing Game

Kayleigh Hyde presented our joint paper on nondeterministic automatic complexity at

COCOON 2014.

In 2015, the paper appeared in Electronic Journal of Combinatorics.

The ideas are implemented in the Complexity Guessing Game!

# Low for random reals and positive-measure domination

Low for random reals and positive-measure domination

Proceedings of the American Mathematical Society **135** (2007), no. 11, 3703—3709 (electronic).

This is a frequently cited paper containing the sometimes-called “Bjorn’s lemma” (in analogy with Zorn’s lemma?) characterizing LR-reducibility. Stronger results were obtained in a later paper which is still to appear in J. LMS.

# Kolmogorov complexity and strong approximation of Brownian motion

Kolmogorov complexity and strong approximation of Brownian motion

(with Tamás Szabados). Proceedings of the American Mathematical Society **139** (2011) no. 9, 3307—3316.

In this email-collaboration paper we improved a bound from Asarin (Kolmogorov’s PhD student) and Pokrovskii’s paper on Kolmogorov complexity and Brownian motion.

# Kolmogorov complexity and the recursion theorem

Kolmogorov complexity and the recursion theorem (with Wolfgang Merkle and Frank Stephan). Transactions of the American Mathematical Society**363** (2011) no. 10, 5465—5480.

arXiv:0901.3933. Preliminary version in STACS 2006,* Lecture Notes in Computer Science,*

vol. 3884, Springer, Berlin, 2006, pp. 149—161.

The groundwork for this paper was laid in Berkeley in 2004 while Merkle and I were both stopping by there. The paper fits in a long line of results saying “DNR is equivalent to…”, in this case to computing a real whose initial segment complexity is sufficiently high.

# A strong law of computationally weak subsets

A strong law of computationally weak subsets

Journal of Mathematical Logic **11** (2011) no. 1, 1—10.

DOI: 10.1142/S0219061311000980

Electronic Colloquium on Computational Complexity, Report No. 150 (2010).

This paper establishes a new statistical law, namely that for each random sequence

$$0111011101101101101\ldots$$

it is possible to replace some of the 1s by 0s (in other words, form a *subset* of 1s) in such a way that no random sequence can be recovered by computational means.

To illustrate, imagine that the new sequence looks like

$$0111010101101000101\ldots$$

Technically the result is that each 2-random set has an infinite subset computing no 1-random set. It is perhaps the main result obtained under Prof. Kjos-Hanssen’s grant NSF DMS-0901020 (2009-2013).

Joseph S. Miller at U. of Wisconsin has established a strengthening of this result replacing 2-random by 1-random, but that result is so far unpublished.

Dr. Bjørn Kjos-Hanssen is a professor at the University of Hawai‘i at Manoa in the Department of Mathematics. His research deals with the abstract theory of computation, computability, randomness and compression algorithms.

Kjos-Hanssen is the author of more than 20 papers in journals including the prestigious *Mathematical Research Letters* and *Transactions of the American Mathematical Society*, and has a PhD from UC Berkeley in the subject **Logic and the Methodology of Science**.

# Superhighness

Superhighness

(with André Nies). Notre Dame Journal of Formal Logic **50** (2009), no. 4, 445—452.

This paper written on Maui has since been superseded in at least two ways.