Will Devanny has become the latest UCI theory student to complete his doctorate, jointly supervised by me and Mike Goodrich.

Since Will came to UCI from CMU in 2012, I’ve published with him on many varied topics: permutation superpatterns and their applications in graph drawing, using Galois theory to show the non-existence of exact algorithms, the hardness of modeling social networks with exponential random graphs, recovering graphs from their joint degree distributions, track layouts of graphs, and even directing vehicle traffic. He also worked on time-windowed queries on timestamped geometric data, and I’ve posted here on a cute algorithmic puzzle he (re)discovered, on what happens to AVL trees when you insert keys in order.

But his dissertation is about none of those things. Instead, it combines the research from three papers that are all loosely connected as variations on sorting. One, “Parallel equivalence class sorting” from SPAA 2016, with Goodrich and former UCI undergraduate Kris Jetviroj, concerns the problem of grouping a given collection of elements into equivalence classes by making as few queries as possible for whether two elements are equivalent to each other. This problem was studied before, but Will proves a new tight lower bound for it in terms of the size of the smallest equivalence class, and shows how to solve it efficiently in parallel. The second, “The online house numbering problem”, with Jeremy Fineman, Goodrich, and Tsvi Kopelowitz, will appear in ESA 2017. It concerns maintaining numerical tags for ordered items (like the houses in a street) allowing insertions of new items while avoiding changing any item’s number too many times. And I hope to post about the third in more detail later, because it’s another joint work that includes me, currently in submission.

Will has already been teaching at Pomona College, and as I understand it has lined up a two-year position there once he finishes at UCI.

Congratulations, Will!