A small approximately min-wise independent family of hash functions

In this paper we give a construction of a small approximately min-wise inde pendent family of hash functions, i.e., a family of hash functions such tha t for any set of arguments X and x is an element of X, the probability that the value of a random function from that family only will be the smallest among all values of that function on X is roughly 1//X/. The number of bits needed to represent each function is O(log n . log 1/epsilon). This constr uction gives a solution to the main open problem of A. Broder ct nl. (in "S TOC'98"). (C) 2001 Academic Press.