Category Archives: research

architectural-blueprint@2x

Lean blueprint projects

Lean is a popular proof assistant. Blueprint projects document Lean projects with Mathlib-style documentation and LaTeX/PDF support. Here are my 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)
product_pages

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.

Screenshot 2023-05-16 at 8.36.51 PM

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.

Slides for October 30

final_606fedbcf8165f00fb8d9c00_638817

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.
  1. KL-randomness and effective dimension under strong reducibility (with David J. Webb). Computability in Europe, Lectures Notes in Computer Science, 2021.
  2. On the degrees of constructively immune sets (with Samuel D. Birns). Computability in Europe, Lectures Notes in Computer Science, 2021.
  3. Strong Medvedev reducibilities and the KL-randomness problem (with David J. Webb). Computability in Europe, Lectures Notes in Computer Science, 2022.
image_6483441
38-example

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