Shattuck_Avenue_Berkeley_Calif

Publications

Journal articles, books, and book chapters

  1. Automatic complexity: a computable measure of irregularity. De Gruyter Series in Logic and Its Applications 12 (2024). Chapter 7 contains material from Conditional automatic complexity and its metrics. COCOON 2023, Lecture Notes in Computer Science 14422 (2024), 15-28.
  2. 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 44 (2024), World Scientific Publishing, Hackensack, NJ. Accepted.
  3. Maximal automatic complexity and context-free languages. Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore 42 (2024), 335--352.
  4. 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 42 (2024), 115--139. Combined final version of two conference papers:
  5. Interpolating between the Jaccard distance and an analogue of the normalized information distance. Journal of Logic and Computation 32 (2022), no. 8, 1611–1623. Preliminary version: Bjørn Kjos-Hanssen, Saroj Niraula, Soowhan Yoon. A parametrized family of Tversky metrics connecting the Jaccard distance to an analogue of the normalized information distance. Lectures Notes in Computer Science 13137, 112--124. Logical Foundations of Computer Science 2022. Formalized at the time of publication.
  6. Bjørn Kjos-Hanssen and Lei Liu: The number of languages with maximum state complexity, Algebra Universalis 83 (2022), no. 3. Lecture Notes in Computer Science 11436 (2019), 394--409. TAMC 2019 (Theory and Applications of Models of Computation).
  7. 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. International Symposium on Artificial Intelligence and Mathematics (ISAIM) 2020. Annals of Mathematics and Artificial Intelligence 90 (2022), no. 1, 93--105.
  8. An incompressibility theorem for automatic complexity. Forum of Mathematics Sigma 9 (2021), E62.
  9. Bjørn Kjos-Hanssen, Automatic complexity of Fibonacci and Tribonacci words. Discrete Applied Mathematics 289 (31 January 2021), 446--454.
  10. Bjørn Kjos-Hanssen and Lu Liu: Extracting randomness within a subset is hard, European Journal of Mathematics 6 (2020), no. 4, 1438–1451.
  11. Only human. Notices of the American Mathematical Society 66 (2019), no. 4, 556--561.
  12. Few paths, fewer words: model selection with automatic structure functions. Experimental Mathematics 28 (2019), no. 1, 121--127.
  13. 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.
  14. 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.
  15. 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.
  16. On the complexity of automatic complexity. Theory of Computing Systems 61 (2017), no. 4, 1427-–1439.
  17. A conflict between some semantic conditions of Carmo and Jones for contrary-to-duty obligations, Studia Logica 105 (2017), no. 1, 173--178.
  18. 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.
  19. 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.
  20. 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.
  21. Pricing complexity options (with M. Alikhani, A. Pakravan, and B. Saadat), Algorithmic Finance 4 (2015), no. 3-4, 127-137.
  22. 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.
  23. 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.
  24. 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.
  25. Algorithmic aspects of Lipschitz functions (with Cameron Freer, André Nies, and Frank Stephan). Computability 3 (2014), no. 1, 45-61.
  26. Randomness extraction and asymptotic Hamming distance (with Cameron Freer). Logical Methods in Computer Science 9 (2013) no. 3, Paper 27.
  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.
  28. Lowness notions, measure, and domination (with Joseph S. Miller and Reed Solomon). Journal of the London Mathematical Society 85 (2012), no. 3, 869–888.
  29. 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.
  30. 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).
  31. 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.
  32. Kolmogorov complexity and strong approximation of Brownian motion (with Tamás Szabados). Proceedings of the American Mathematical Society 139 (2011) no. 9, 3307—3316.
  33. The probability distribution as a computational resource for randomness testing. Journal of Logic and Analysis 2 (2010), no. 10, 1—13.
  34. Higher Kurtz randomness (with André Nies, Frank Stephan, and Liang Yu). Annals of Pure and Applied Logic 161 (2010), no. 10, 1280—1290.
  35. Lattice initial segments of the hyperdegrees (with Richard A. Shore). Journal of Symbolic Logic 75 (2010), no. 1, 103—130.
  36. Superhighness (with André Nies). Notre Dame Journal of Formal Logic 50 (2009), no. 4, 445—452.
  37. Finding paths through narrow and wide trees (with Stephen E. Binns). Journal of Symbolic Logic 74 (2009), no. 1, 349—360.
  38. Infinite subsets of random sets of integers. Mathematical Research Letters 16 (2009), no. 1, 103—110.
  39. 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.
  40. 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.
  41. 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.
  42. Low for random reals and positive-measure domination. Proceedings of the American Mathematical Society 135 (2007), no. 11, 3703—3709 (electronic).
  43. 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.
  44. 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).
  45. Comparing DNR and WWKL (with Klaus Ambos-Spies, Steffen Lempp, and Theodore A. Slaman). Journal of Symbolic Logic 69 (2004), no. 4, 1089—1104.
  46. Local initial segments of the Turing degrees. Bulletin of Symbolic Logic 9 (2003), no. 1, 26—36.

Conference papers without a journal version yet

  1. The strength of the Besicovitch-Davies theorem (with Jan Reimann), Computability in Europe, Lecture Notes in Computer Science 6158 (2010), 229—238.
  2. Numberings and randomness (with Katie Brodhead). Computability in Europe, Lecture Notes in Computer Science 5635 (2009), 49—58.
  3. 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).
  4. Kjos-Hanssen: A rigid cone in the truth-table degrees with jump, Downey Festschrift, Lecture Notes in Computer Science 10010 (2017), 487--500.
  5. Superposition as memory: unlocking quantum automatic complexity. Lecture Notes in Computer Science 10240 (2017), 160-169. Unconventional Computation and Natural Computation (UCNC) 2017.
  6. KL-randomness and effective dimension under strong reducibility (with David J. Webb). Computability in Europe, Lectures Notes in Computer Science 12813 (2021), 457--468.
  7. On the degrees of constructively immune sets (with Samuel D. Birns). Computability in Europe, Lectures Notes in Computer Science 12813 (2021), 50--59.
  8. Bjørn Kjos-Hanssen and David J. Webb. Strong Medvedev reducibilities and the Kolmogorov-Loveland randomness problem. Lecture Notes in Computer Science 13359 (2022), 151--161, Computability in Europe 2022.

arXiv only

  1. Lattice initial segments of the Turing degrees, doctoral dissertation, Logic and the Methodology of Science, University of California, Berkeley, 2002, iii+89 pages.
  2. Effective Banach spaces, Master's thesis, Mathematics, University of Oslo, 1997.
  3. 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.
  4. Google distance between words (with Alberto J. Evangelista). Presented at Frontiers in Undergraduate Research, University of Connecticut, 2006.

Comment

For a lot more on the Turing automorphism problem by Slaman and Woodin, see their manuscript draft.

Textbook

  1. Kjos-Hanssen and Birns: Statistics for Calculus Students.  Open Education Resources (OER), Outreach College, University of Hawaii at Manoa, February 21, 2019. (Permalink)