The well-known definition of Hamming distance between two vectors is generalized to the case of s vectors. This produces a new notion, hash distances of a code. The second hash distance coincides with the usual minimal (Hamming) distance of a code. The so-called sets of perfect hash functions, widely studied in combinatorics and computer science, are, in fact, the same as codes with the s-th hash distance at least 1.

We study hash distances of codes by coding-theoretic methods trying to obtain good upper and lower bounds on the maximal cardinality of codes with given s-th distance.

Among the new results let us mention an upper bound, which is better than the celebrated Friedman-Komlos bound for the size of sets of perfect hash functions, and an application of linear codes with large hash distance to constructing sets of perfect hash functions with ``simple realization''. We also discuss one nice combinatorial problem arising from the question when linear codes with nonzero hash distance exist. Many open problems will be set.

This talk is based on a joint paper of L.Bassalygo, M.Burmester, A.Dyachkov, and the speaker.

Back to Workshop Schedule