CSE 591 Perfect Hashing


Contact Information:
I am located in Brickyard 444. Contact me by email at Charles.Colbourn@asu.edu as the most reliable way to reach me.
The class schedule is T Th 1:30-2:45 in BYAC 260.
Background in algorithms, data structures, and discrete mathematics will be useful. Interest in cryptography will be helpful.
In 1984 Mehlhorn developed a theory of perfect hashing to avoid the need for collision resolution in lookup of programming language keywords. In the process, he developed perfect families of hash functions. The pervasiveness of perfect hash families since that time is remarkable: They arise in derandomization of probabilistic algorithms, construction of cryptographic protocols, and explicit constructions of a wide variety of other combinatorial objects.

Despite their importance, they remain hard to construct in general. Probabilistic techniques are very effective at answering asymptotic existence questions, but have limited applications to problems that arise in practice. Combinatorial, algebraic, and geometric tools have all been effectively employed to make specific perfect hash families, but at present all handle a small fraction of the cases of interest. Hence we often resort to computation. Exhaustive methods (backtracking, integer linear programming) appear to succeed only for very small problems. Heuristic methods (simulated annealing, tabu search, constraint satisfaction techniques, genetic algorithms) extend the range of computation, at the expense of obtaining upper bounds on the sizes of families rather than exact results. Even so, the more sophisticated methods do not extend the range of computational results very far, due to the combinatorial explosion of the search space.

Consequently much interesting work remains to be done, and we will identify next steps that may substantially improve our understanding of perfect hash families. At the same time, we will explore some of the ways in which they are used in applications in cryptography, interaction testing, and derandomization.

The goal is to provide a context in each of the relevant background areas to underpin a detailed investigation by individual students into one of them.


Assessment: