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:
- a project counting 100%.
The main features are:
- the topic is different for each individual, and is chosen by the
student. Particular project topics should be discussed with me to ensure
that they are reasonable.
- You may choose a project which is a literature review, an
implementation and experimentation, or theoretical research (i.e., you
may focus your activities on reading, coding, or thinking -- but, of course,
you must do all three to some degree!)
- Plan on making an in-class presentation (duration: 25 minutes plus 12.5 minutes questions) to the class.
- Due date is at the final exam time for the course.
Start on the project
early!
- Feel free to consult anyone, especially me, about the project as you
work on it.
- The most important thing that I want to see in the projects is a
creative and innovative approach that clearly demonstrates a deep understanding
of some topic relevant to the course. In general, depth is preferred to
breadth, and your ideas are preferred to someone else's.
- No tests or examinations are planned.