Realistic Hashing, Online Sorting, and Constrained Correlation Clustering

This thesis summarizes the work I’ve done during my PhD program at BARC, covering new results in Realistic Hashing, Online Sorting, and Constrained Correlation Clustering.
Realistic Hashing revolves around the study of realistically implementable families of functions which carry strong mathematical guarantees. Here we build upon the work of Dahlgaard, Knudsen, Rotenberg, and Thorup [DKRT15], introducing a new tabulation-based hash function, Tornado Tabulation, giving both new and stronger guarantees than Mixed Tabulation.
Online Sorting is a new problem introduced by Aamand, Abrahamsen, Beretta, and Kleist [AABK23]. Real values arrive one by one, and we must place them into an (approximately) sorted list without moving previous elements. We strengthen their lower bound to also cover randomized algorithms in the oblivious setting, and show (positive and negative) results for a range of new variations of the problem.
Finally, Constrained Correlation Clustering, introduced by van Zuylen, Hegde, Jain, and Williamson [vZHJW07], is a generalization of the well-known Correlation Clustering problem where certain preferences are promoted to hard constraints, thus restricting the set of valid solutions. We present a new algorithm that is significantly faster than the one from [vZHJW07], at the cost of providing a slightly worse (but still constant) approximation factor.