[Resource Topic] 2003/017: Perfect Hash Families with Few Functions

Welcome to the resource topic for 2003/017

Perfect Hash Families with Few Functions

Authors: Simon R. Blackburn


An {\em (s;n,q,t)-perfect hash family} is a set of functions
\phi_1,\phi_2,\ldots ,\phi_s from a set V of cardinality n to a
set F of cardinality q with the property that every t-subset of
V is injectively mapped into F by at least one of the functions

The paper shows that the maximum value n_{s,t}(q) that n can take
for fixed s and t has a leading term that is linear in q if and only if
t>s. Moreover, for any s and t such that t>s, the paper shows how to
calculate the coefficient of this linear leading term; this
coefficient is explicitly calculated in some cases. As part of this
process, new classes of good perfect hash families are constructed.

ePrint: https://eprint.iacr.org/2003/017

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .