Optimal Linear Perfect Hash Families

LetVbe a set of ordernand letFbe a set of orderq. A setS⊆{φ: V→F} of functions fromVtoFis an (n, q, t)-perfect hash familyif for allX⊆Vwith |X|=t, there existsφ∈Swhich is injective when restricted toX. Perfect hash families arise in compiler design, in circuit complexity theory and in cryptography. LetSbe an (n, q, t)-perfect hash family. The paper provides lower bounds on |S|, which better previously known lower bounds for many parameter sets. The paper exhibits new classes of perfect hash families which show that these lower bounds are realistic.