Speaker
Description
The monotone minimal perfect hash (MMPH) is a data structure that, for a set of n integers k1<...<kn from an interval [1..u], supports the following queries: given x, the query either returns i such that ki = x if such i exists, or returns any number otherwise. The MMPH is a well-known algorithmic workhorse with many applications, both theoretical and practical. The most space-efficient known MMPHs utilize only O(n log log log u) bits of space. Recently, Assadi, Farach-Colton, and Kuszmaul proved that, surprisingly, this weird space bound is tight in the worst case, for a very broad range of parameters n and u (essentially including all interesting cases). This result, presented in their paper "tight bounds for monotone minimal perfect hashing" at SODA'23, was obtained using a series of non-trivial combinatorial techniques like fractional chromatic numbers, LP duality, and non-standard graph products. In this talk, a simplified (albeit still non-trivial) approach for the proof is presented using only relatively elementary combinatorial methods.
