open notebook
    William DeMeo


I am a postdoc in the Math Department at University of Hawaii (2016–2017). In fall 2017 I will move to University of Colorado, Boulder.

I have worked at Iowa State University (2014–2016) and University of South Carolina (2012–2014).

My primary research area is universal algebra; current projects focus on lattice theory, computational complexity, and universal algebraic approaches to constraint satisfaction problems. Other research interests include logic, computability theory, type theory, category theory, functional programming, dependent types, and proof-carrying code.

Most of my research papers are posted on my Math arXiv page or my CS arXiv page. A more comprehensive collection of my work resides in my Github repositories.

cv      email       github       pgp key

found on

Congruences of Partial Algebras

- - posted in Lattice Theory, Partial Algebras, Universal Algebra

The repository par-alg-rep contains some notes describing a few results that we worked out in the fall of 2016, while I was a postdoc at University of Hawaii, although the main result—a straight-forward proof of the fact that every finite lattice is the congruence lattice of a finite partial algebra—was discovered during a visit to Chapman University in October 2016.

3-SAT and Partition Lattices

- -

It is not hard to see that 3-SAT reduces to the problem of deciding whether all coatoms in a certain partition lattice are contained in the union of a collection of certain principal filters. Therefore, the latter problem, which we will call the covered coatoms problem (CCP), is NP-complete. In this post we simply define CCP. Later we check that 3-SAT reduces to CCP, and then develop some ideas about constructing a feasible algorithm to solve CCP.


- -

Equivalence of algebraic structures

Consider two finite algebras that are the same except for a relabeling of the operations. Our intuition tells us that these are simply different names for the same mathematical structure. Formally, however, not only are these distinct mathematical objects, but also they are nonisomorphic.

Isotopy is another well known notion of “sameness” that is broader than isomorphism. However, I recently proved a result that shows why isotopy also fails to fully capture algebraic equivalence.


- - posted in Resources

I started a GitHub repository called TypeFunc in an effort to get my head around the massive amount of online resources for learning about type theory, functional programming, category theory, $\lambda$-calculus, and connections between topology and computing.