✦ LIBER ✦

Optimal Linear Perfect Hash Families

✍ Scribed by Simon R Blackburn; Peter R Wild

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 333 KB
Volume: 83
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1998.2876

No coin nor oath required. For personal study only.

✦ Synopsis

Let V be a set of order n and let F be a set of order q. A set S [,: V Ä F ] of functions from V to F is an (n, q, t)-perfect hash family if for all X V with |X | =t, there exists , # S which is injective when restricted to X. Perfect hash families arise in compiler design, in circuit complexity theory and in cryptography. Let S be 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.

📜 SIMILAR VOLUMES

Optimal linear perfect hash families wit

Optimal linear perfect hash families with small parameters

✍ S. G. Barwick; Wen-Ai Jackson; Catherine T. Quinn 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 146 KB

## Abstract A linear (__q__^__d__^, __q__, __t__)‐perfect hash family of size __s__ consists of a vector space __V__ of order __q__^__d__^ over a field __F__ of order __q__ and a sequence ϕ~1~,…,ϕ~__s__~ of linear functions from __V__ to __F__ with the following property: for all __t__ subsets __X_

Some recursive constructions for perfect

Some recursive constructions for perfect hash families

✍ M. Atici; S. S. Magliveras; D. R. Stinson; W.-D. Wei 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 452 KB

An (n, m, w)-perfect hash family is a set of functions F such that f : (1

Perfect Hash Families: Probabilistic Met

Perfect Hash Families: Probabilistic Methods and Explicit Constructions

✍ Simon R. Blackburn 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 113 KB

An (n, q, t)-perfect hash family of size s consists of a set V of order n, a set F of order q, and a sequence , 1 , , 2 , ..., , s of functions from V to F with the following property. For all t-subsets X V, there exists i # [1, 2, ..., s] such that , i is injective when restricted to X. An (n, q, t

Explicit Constructions of Perfect Hash F

Explicit Constructions of Perfect Hash Families from Algebraic Curves over Finite Fields

✍ Huaxiong Wang; Chaoping Xing 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 149 KB

Let A be a set of order n and B be a set of order m. An (n, m, w)-perfect hash family is a set H of functions from A to B such that for any X A with |X |=w, there exists an element h # H such that h is one-to-one when restricted to X. Perfect hash families have many applications to computer science,

New constructions for perfect hash famil

New constructions for perfect hash families and related structures using combinatorial designs and codes

✍ D. R. Stinson; R. Wei; L. Zhu 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB 👁 1 views

In this paper, we consider explicit constructions of perfect hash families using combinatorial methods. We provide several direct constructions from combinatorial structures related to orthogonal arrays. We also simplify and generalize a recursive construction due to Atici, Magliversas, Stinson and