- First-Derivative Test (2024, with Patrick Massot and Floris van Doorn)
- Equivalence between one-point compactification of $\mathbb R$ and the projective line (2024, with Oliver Nash)
Category Archives: research
Lean blueprint projects
- Marginis – formalia marginalia for the Journal of Logic and Analysis
- Protein folding – formalizations related to the paper Nonmonotonicity of protein folding under concatenation
- Automatic complexity – formalized exercise solutions for my book
- Dyadic deontic logic – formalized results from a paper in preparation (with Rachelle Edwards)
- Jaccard – formalization research paper Interpolating between the Jaccard distance and an analogue of the normalized information distance (Journal of Logic and Computation, 2022)
Formal marginalia in computability theory
A talk I gave at the ASL Annual Meeting in Ames, Iowa, May 15, 2024.
Slides:
ASL-2024-slides-Kjos-Hanssen
Automatic complexity of distinguishing
My book “Automatic complexity: a computable measure of irregularity” was published by de Gruyter on February 19, 2024. It concerns a version of Sipser’s complexity of distinguishing that was introduced by Shallit and Wang in 2001 and has been developed by me and others since 2013.
Erratum
Theorem 6.6: Two constructions $M_1\times_1 M_2$ and $M_1\times_2 M_2$ are described. The text suggests that $\times_1$ is used for the theorem, but actually $\times_2$ should be used. The operation $\times_1$ can be used to prove the inequality $A_N(x)\le A_N(x\mid y)\cdot A_N(y)$ instead.
Math 100 student’s protein folding research
Madison Koskey had the highest score in the class on this project task:
Fold an idealized protein known as S64 to obtain a highest possible score in the hydrophobic-polar protein folding model in three dimensions.
This problem was studied by Lesh, Mitzenmacher, and Whitesides (2003).
Above we see Madison’s intricate folding of S64 which earned a score of 27.
To try your hand at rotating it in 3D, go directly to this link.
Recent PhDs
Three new papers
with my recent PhDs Birns (2023, left) and Webb (2022, right). Webb is now an Assistant Professor at Chaminade University, and Birns is a data scientist at Pacific Life in California.- 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.
- Strong Medvedev reducibilities and the KL-randomness problem (with David J. Webb). Computability in Europe, Lectures Notes in Computer Science, 2022.
The number of languages with maximum state complexity
Lei Liu completed her Master’s degree with the project title Complexity of Options in 2017.
An extension to monotone options (pictured) was presented at
ALH-2018. The new paper is called The number of languages with maximum state complexity and has been accepted for TAMC 2019.
As of 2022, the paper has been through 7 revisions and has been accepted for publication in the journal Algebra Universalis.
Some of the 168 monotone Boolean functions of 4 variables
- Slides for ALH 2018
- Slides for TAMC 2019