Conference papers submitted for journal publication
- Shift registers fool finite automata. Lecture Notes in Computer Science 10388 (2017), 170-181. Workshop on Logic, Language, Information and Computation (WoLLIC) 2017.
- Permutations of the integers induce only the trivial automorphism of the Turing degrees, Downey Festschrift, Lecture Notes in Computer Science 10010 (2017) 599--607.
Other recent conference papers
- Superposition as memory: unlocking quantum automatic complexity. Lecture Notes in Computer Science 10240 (2017), 160-169. Unconventional Computation and Natural Computation (UCNC) 2017.
- Effective bi-immunity and randomness (with Achilles Beros and Mushfeq Khan), Downey Festschrift, Lecture Notes in Computer Science 10010 (2017) 633--643.
- A rigid cone in the truth-table degrees with jump, Downey Festschrift, Lecture Notes in Computer Science 10010 (2017), 487--500.
- Beros, Khan, Kjos-Hanssen, Nies:
A computability hierarchy for eventually different functions.
In preparation for CiE 2018.
- Beros, Khan, Kjos-Hanssen:
Finding paths through narrow and wide trees, reconsidered
- Beros, Kjos-Hanssen, Shallit, and Yogi:
The asymptotic number of words with given automatic complexity
- Kjos-Hanssen: A characterization of words of quantum automatic complexity equal to two
- Few paths, fewer words: model selection with automatic structure functions. Experimental Mathematics 28 (2019), no. 1, to appear.
- On the complexity of automatic complexity. Theory of Computing Systems 61 (2017), no. 4, 1427-–1439.
- A conflict between some semantic conditions of Carmo and Jones for contrary-to-duty obligations, Studia Logica 105 (2017), no. 1, 173--178.
- Covering the recursive sets (with Frank Stephan and Sebastiaan Terwijn), Annals of Pure and Applied Logic 168 (2017), no. 4, 804--823. Computability in Europe, Lecture Notes in Computer Science 9136 (2015), 44—53.
- The Strength of the Grätzer-Schmidt theorem (with Katie Brodhead, Mushfeq Khan, William A. Lampe, Paul Kim Long V. Nguyen, and Richard A. Shore). Archive for Mathematical Logic 55 (2016), no. 5, 687—704. Computability in Europe, Lecture Notes in Computer Science 5635 (2009), 59—67.
- Kolmogorov structure functions for automatic complexity. Theoretical Computer Science 607 (2015), no. 3, 435—445. Lecture Notes in Computer Science (COCOA 2014): Kolmogorov structure functions for automatic complexity in computational statistics.
- Pricing complexity options (with M. Alikhani, A. Pakravan, and B. Saadat), Algorithmic Finance 4 (2015), no. 3-4, 127-137.
- Nondeterministic automatic complexity of overlap-free and almost square-free words (with K. Hyde). Electronic Journal of Combinatorics 22 (2015), no. 3, Paper 3.22, 18 pp.
Nondeterministic automatic complexity of almost square-free and strongly cube-free words, COCOON 2014, Lecture Notes in Computer Science 8591 (2014), 61—70.
- Algorithmic randomness for Doob's martingale convergence theorem in continuous time (with Paul Kim Long V. Nguyen and Jason M. Rute). Logical Methods in Computer Science 10 (2014) no. 4, Paper 12.
- How much randomness is needed for statistics? (with Antoine Taveneaux and Neil Thapen). Annals of Pure and Applied Logic 165 (2014), no. 9, 1470-1483. Computability in Europe, Lecture Notes in Computer Science 7318 (2012), 395—404.
- Algorithmic aspects of Lipschitz functions (with Cameron Freer, André Nies, and Frank Stephan). Computability 3 (2014), no. 1, 45-61.
- Randomness extraction and asymptotic Hamming distance (with Cameron Freer). Logical Methods in Computer Science 9 (2013) no. 3, Paper 27.
- Arithmetic complexity via effective names for random sequences (with Frank Stephan and Jason R. Teutsch). ACM Transactions on Computational Logic 13, no. 3 (July 2012), Art. 24, 18 pp.
- Lowness notions, measure, and domination (with Joseph S. Miller and Reed Solomon). Journal of the London Mathematical Society 85 (2012), no. 3, 869–888.
- Martin-Löf randomness and Galton-Watson processes (with David Diamondstone). Annals of Pure and Applied Logic 163 (2012), no. 5, 519-529. Members of random closed sets. Computability in Europe, Lecture Notes in Computer Science 5635 (2009), 144—153.
- A strong law of computationally weak subsets,
Journal of Mathematical Logic 11 (2011) no. 1, 1—10. See also Electronic Colloquium on Computational Complexity, Report No. 150 (2010).
- Kolmogorov complexity and the recursion theorem (with Wolfgang Merkle and Frank Stephan). Transactions of the American Mathematical Society 363 (2011) no. 10, 5465—5480. STACS 2006, Lecture Notes in Computer Science 3884 (2006), pp. 149—161.
- Kolmogorov complexity and strong approximation of Brownian motion (with Tamás Szabados). Proceedings of the American Mathematical Society 139 (2011) no. 9, 3307—3316.
- The probability distribution as a computational resource for randomness testing. Journal of Logic and Analysis 2 (2010), no. 10, 1—13.
- Higher Kurtz randomness (with André Nies, Frank Stephan, and Liang Yu). Annals of Pure and Applied Logic 161 (2010), no. 10, 1280—1290.
- Lattice initial segments of the hyperdegrees (with Richard A. Shore). Journal of Symbolic Logic 75 (2010), no. 1, 103—130.
- Superhighness (with André Nies). Notre Dame Journal of Formal Logic 50 (2009), no. 4, 445—452.
- Finding paths through narrow and wide trees (with Stephen E. Binns). Journal of Symbolic Logic 74 (2009), no. 1, 349—360.
- Infinite subsets of random sets of integers. Mathematical Research Letters 16 (2009), no. 1, 103—110.
- Effective dimension of points visited by Brownian motion (with Anil Nerode). Theoretical Computer Science 410 (2009), no. 4-5, 347—354. The law of the iterated logarithm for algorithmically random paths of Brownian motion. Logical Foundations of Computer Science, Lecture Notes in Computer Science 4514 (2007), pp. 310—317.
- 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.
- Low for random reals and positive-measure domination. Proceedings of the American Mathematical Society 135 (2007), no. 11, 3703—3709 (electronic).
- On a conjecture of Dobrinen and Simpson concerning almost everywhere domination (with Stephen Binns, Manuel Lerman, and Reed Solomon). Journal of Symbolic Logic 71 (2006), no. 1, 119—136.
- Lowness for the class of Schnorr random reals (with André Nies and Frank Stephan). SIAM Journal on Computing 35 (2005), no. 3, 647—657 (electronic).
- Comparing DNR and WWKL (with Klaus Ambos-Spies, Steffen Lempp, and Theodore A. Slaman). Journal of Symbolic Logic 69 (2004), no. 4, 1089—1104.
- Local initial segments of the Turing degrees. Bulletin of Symbolic Logic 9 (2003), no. 1, 26—36.
- The strength of some combinatorial principles related to Ramsey's theorem (with Denis R. Hirschfeldt, Carl G. Jockusch, Steffen Lempp, and Theodore A. Slaman.) Computational Prospects of Infinity. Part II: Presented Talks, Lecture Notes Series, Institute of Mathematical Sciences, National University of Singapore 15, World Scientific Publishing, Hackensack, NJ, 2008, pp. 143—162.
Conference papers without a journal version
- The strength of the Besicovitch-Davies theorem (with Jan Reimann), Computability in Europe, Lecture Notes in Computer Science 6158 (2010), 229—238.
- Numberings and randomness (with Katie Brodhead). Computability in Europe, Lecture Notes in Computer Science 5635 (2009), 49—58.
- Lattice initial segments of the Turing degrees, doctoral dissertation, Logic and the Methodology of Science, University of California, Berkeley, 2002, iii+89 pages.
- Effective Banach spaces, Master's thesis, Mathematics, University of Oslo, 1997.
- Models of the Chisholm set, term paper for Filosofi hovedfag spesialområde 1, Fall 1996, University of Oslo. First cited in Carmo and Jones, Deontic logic and contrary-to-duties, Handbook of Philosophical Logic, 2002.
- Google distance between words (with Alberto J. Evangelista). Presented at Frontiers in Undergraduate Research, University of Connecticut, 2006.
Professor of Mathematics, University of Hawaii at Manoa