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.

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.

Higher Kurtz randomness

Higher Kurtz randomness
(with André Nies, Frank Stephan, and Liang Yu). Annals of Pure and Applied Logic 161 (2010), no. 10, 1280—1290.

I visited Liang Yu at Nanjing University, China in 2008 and 2009. The collaboration for this paper however was later done by email plus a strategy meeting in Marseille in 2009.

Effective dimension of points visited by Brownian motion

Effective dimension of points visited by Brownian motion
(with Anil Nerode). Theoretical Computer Science 410 (2009), no. 4-5, 347—354.

Preliminary version: The law of the iterated logarithm for algorithmically random paths of Brownian motion.
Logical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 4514, Springer, Berlin, 2007, pp. 310—317.

In this paper we answered a question of Fouché regarding algorithmically random Brownian motion. The key idea was to use Carathéodory’s measure algebra isomorphism theorem.

Infinite subsets of random sets of integers

Infinite subsets of random sets of integers
Mathematical Research Letters 16 (2009), no. 1, 103—110.

This paper was written in Fall 2007 in Hawaii. It was superseded by a paper in J. Mathematical Logic 2011.

Finding paths through narrow and wide trees

History of the paper

2006

The paper was written at UConn.

2009

Paper appeared in print:

Finding paths through narrow and wide trees
(with Stephen E. Binns). Journal of Symbolic Logic 74 (2009), no. 1, 349—360.

2012

Laurent Bienvenu and Paul Shafer discovered an apparent error in the proof of Lemma 4.6. There it is stated that A wtt-reduces to B; however, it seems that the reduction of A to B also requires oracle access to f. Corollary 4.7 also seems false (take f to be a ML random of hyperimmune-free degree, and A=f; then A is complex but not f-complex).

Self-embeddings of computable trees

Self-embeddings of computable trees (with Stephen Binns, Manuel Lerman, Jim Schmerl, and Reed Solomon).
Notre Dame Journal of Formal Logic 49 (2008), no. 1, 1—37.

I was probably the least-involved of the five authors of this paper, which was written in 2005-2006 at UConn.