𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Combinatorial techniques for universal hashing

✍ Scribed by D.R. Stinson

Book ID
104147809
Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
498 KB
Volume
48
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

The idea of a universal class of hash functions is due to Carter and Wegman. The goal is to define a collection of hash functions in such a way that a random choice of a function in the class yields a low probability that any two distinct inputs will collide. In this paper, we present some characterizations of universal classes of hash functions in terms of combinatorial designs such as resolvable balanced incomplete block designs and orthogonal arrays. The two classes of hash functions that we study are called optimally universal and strongly universal. We show that optimally universal classes of hash functions are equivalent to resolvable balanced incomplete block designs and strongly universal classes are equivalent to orthogonal arrays. Consequently, known classes of combinatorial designs yield new, small, and efficient classes of universal hash functions.

πŸ“œ SIMILAR VOLUMES

A combinatorial characterization of cert
A combinatorial characterization of certain universal classes of hash functions
✍ Tran van Trung πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 303 KB

## Abstract A new lower bound on the size of ϡ‐almost strongly universal~2~ classes of hash functions has recently been obtained by Stinson [8]. In this article we present a characterization of Ο΅ βˆ’ ASU~2~ classes of hash functions meeting the Stinson bound in terms of combinatorial designs. Β© 1994

Universal cycles for combinatorial struc
Universal cycles for combinatorial structures
✍ Fan Chung; Persi Diaconis; Ron Graham πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 836 KB

Chung, F., P. Diaconis and R. Graham, Universal cycles for combinatorial structures, Discrete Mathematics 110 (1992) 43-59 In this paper, we explore generalizations of de Bruijn cycles for a variety of families of combinatorial structures, including permutations, partitions and subsets of a finite