The alt-comm repository contains a note giving an alternate decription of the (non-modular) commutator that yields a polynomial time algorithm for computing it. This is inspired by the alternate description of the commutator given by Kearnes in .
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.
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.
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.
The questions below appeared on an online test administered by Jane Street Capital Management to assess whether a person is worthy of a phone interview.
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.
Suppose the lattice shown below is a congruence lattice of an algebra.
Claim: If the three $\alpha_i$’s pairwise permute, then all pairs in the lattice permute.
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.
In the Overalgebras GitHub repo resides the article Expansions of finite algebras and their congruence lattices, Algebra Universalis, 69, 2013. Also included is the GAP software I wrote for constructing new finite algebras by extending and expanding transitive G-sets, as described in the paper.