#### Submitted 2021

- An incompressibility theorem for automatic complexity.
- Bjørn Kjos-Hanssen, Saroj Niraula, Soowhan Yoon, Sabrina Hardisty, Guanhong Li, and Jacqueline Millard. A 1-parameter family of metrics connecting Jaccard distance to normalized information distance.

#### Submitted 2020

- Bjørn Kjos-Hanssen, Clyde James Felix, Sun Young Kim, Ethan Lamb, and Davin Takahashi, VC-dimensions of nondeterministic finite automata for words of equal length. Electronic proceedings of
*International Symposium on Artificial Intelligence and Mathematics*(ISAIM) 2020. Journal version submitted 04 Apr 2020, under review since 08 Oct 2020, under revision since 08 Feb 2021.

#### Submitted 2019

- Bjørn Kjos-Hanssen and Lei Liu: The number of languages with maximum state complexity,
*Algebra Universalis*(resubmitted 20 Jan 2021).*Lecture Notes in Computer Science***11436**(2019), 394--409. TAMC 2019 (Theory and Applications of Models of Computation).

### Journal articles

- Bjørn Kjos-Hanssen, Automatic complexity of Fibonacci and Tribonacci words.
*Discrete Applied Mathematics***289**(31 January 2021), 446--454. - Bjørn Kjos-Hanssen and Lu Liu: Extracting randomness within a subset is hard,
*European Journal of Mathematics***6**(2020), no. 4, 1438–1451. - Only human.
*Notices of the American Mathematical Society***66**(2019), no. 4, 556--561. - Few paths, fewer words: model selection with automatic structure functions.
*Experimental Mathematics***28**(2019), no. 1, 121--127. - Downey, Hirschfeldt and Kjos-Hanssen: Preface. Special issue on "Computability, complexity and randomness'' (CCR 2016). Held in Honolulu, January 4-8, 2016.
*Theory of Computing Systems***62**(2018) no. 7, 1553–1554. - Automatic complexity of shift register sequences. Discrete Mathematics
**341**(2018), no. 9, 2409–2417.*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, Bulletin of Symbolic Logic
**24**(2018), no. 2, 165-174. Downey Festschrift,*Lecture Notes in Computer Science***10010**(2017) 599--607. - 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.

#### Book and book chapters

- Kjos-Hanssen and Birns: Statistics for Calculus Students.
`http://hdl.handle.net/10790/4572`

Open Educational Resources (OER) textbook, Outreach College, University of Hawaii at Manoa, February 21, 2019. - 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. *Immunity, diagonalisation and the complexity of mass problems*(with Achilles Beros, Mushfeq Khan, and Andre Nies), Aspects of Computation. Lecture Notes Series, Institute of Mathematical Sciences, National University of Singapore**39**, World Scientific Publishing, Hackensack, NJ (accepted). Combined final version of two conference papers:- Beros, Khan, Kjos-Hanssen, and Nies: From eventually different functions to pandemic numberings,
*Lecture Notes in Computer Science***10936**(2018), 97--106. Computability in Europe 2018. - Beros, Khan, and Kjos-Hanssen: Effective bi-immunity and randomness, Downey Festschrift,
*Lecture Notes in Computer Science***10010**(2017) 633--643.

- Beros, Khan, Kjos-Hanssen, and Nies: From eventually different functions to pandemic numberings,
- A tractable case of the Turing automorphism problem: bi-uniformly $E_0$-invariant Cantor homeomorphisms. Higher recursion theory and set theory. Lecture Notes Series, Institute of Mathematical Sciences, National University of Singapore
**40**, World Scientific Publishing, Hackensack, NJ. Accepted.

#### Conference papers without a journal version yet

- 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. - Beros, Kjos-Hanssen, and Yogi: Planar digraphs for automatic complexity,
*Lecture Notes in Computer Science***11436**(2019), 59--73. TAMC 2019 (Theory and Applications of Models of Computation). - Kjos-Hanssen: A rigid cone in the truth-table degrees with jump, Downey Festschrift,
*Lecture Notes in Computer Science***10010**(2017), 487--500. - KL-randomness and effective dimension under strong reducibility (with David J. Webb). Computability in Europe, Lectures Notes in Computer Science, 2021.
- On the degrees of constructively immune sets (with Samuel D. Birns). Computability in Europe, Lectures Notes in Computer Science, 2021.

### arXiv only

- 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.

#### In quarantine

- Counting pure states: a quantum variant of automatic complexity. Journal version. Conference version: Superposition as memory: unlocking quantum automatic complexity.
*Lecture Notes in Computer Science***10240**(2017), 160-169. Unconventional Computation and Natural Computation (UCNC) 2017.