open notebook
    William DeMeo


I am a Visiting Assistant Professor at University of Hawaii.

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, programming languages and functional programming. Most of my work can be found on the arXiv or github.

The page you are reading is my open notebook, where I gather thoughts and ideas about projects or problems, and keep notes about subjects I’m learning or researching. The posts are usually rough and maybe misguided. This is a notebook for doing research. It is not a blog.

cv      email       pgp key

found on

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.


- -

What does a nonabelian group sound like?

The GroupSound project is about harmonic analysis on finite groups. Classical dsp filtering algorithms can be implemented as operations involving functions (e.g., audio signals) defined on a finite group. That is, the group serves as the domain, or “index set,” of the functions. In this project, we explore the idea of using the finite group as an adjustable parameter of a digital audio filter.

Cloning an Octopress Repo

- -

When attempting to clone my Octopress repository on a new machine, I had the same Updates were rejected problem that is described on this page. Based on the information provided on that page, combined with a few other commands required for Ubuntu machines, this post provides instructions for cloning an Octopress repository.