Here are a few demonstrations of algorithms that I have designed. The main academic motivation for these algorithms is usually some theoretical goal like having running time polynomial in the size of the input, or being optimal with respect to some parameter. These can be nice measures of an algorithm’s quality or ingenuity, but scoring well in these areas says little about the practical utility of an algorithm.
This page is a work in progress, I add demonstrations from time-to-time.
My work on graph colouring has connected the occupancy method with a greedy fractional colouring algorithm and later with a method for list-colouring based on entropy compression and the Lovász local lemma. The underlying probability and optimisation work is purely theoretical and requires no computer implementation, but the colouring algorithms are demonstrated here.
One of the major breakthroughs in approximate counting in the 2010s was the identification of a computational threshold for antiferromagnetic spin models that coincides with a physical phase transition for such systems. More recently, Will Perkins and I have identified a similar computational transition for the problem of approximating the number of independent sets of a given size in bounded-degree graphs. The algorithmic side uses Markov chain Monte Carlo methods to sample an independent set of the desired size, and we show that our algorithm is optimal in terms of the permitted size by showing that at larger sizes the algorithm could be used to solve an NP-hard problem.
The problem of partitioning a (planar) graph into connected subsets of equal size (or weight, in the case of vertex weights) has applications in political science: how should the precincts of a state be grouped into Congressional districts?