OPTIMAL LINEAR PERFECT HASH FAMILIES

Let V be a set of order n and let F be a set of order q. A set S subse t of or equal to {phi: V --> F} of functions from V to F is an (n, q, t)-perfect hash family if for all X subset of or equal to V with \X\ = t, there exists dr ES which is injective when restricted to X. Perfec t hash families arise in compiler design, in circuit complexity theory and in cryptography. Let S be an (n, q, t)-perfect hash family. The p aper provides lower bounds on \S\, which better previously known lower bounds for many parameter sets. The paper exhibits new classes of per fect hash families which show that these lower bounds are realistic. ( C) 1998 Academic Press.