Completeness and robustness properties of min-wise independent permutations
Andrei Broder, Michael Mitzenmacher · Random Structures and Algorithms · 2000
We provide several new results related to the concept of min-wise independence. Our main result is that any randomized sampling scheme for the relative intersection of sets based on testing equality of samples yields an equivalent min-wise independent family. Thus, in a certain sense, min-wise independent families are “complete” for this type of estimation. We also discuss the notion of robustness, a concept extending min-wise independence to allow more efficient use of it in practice. A surprising result arising from our consideration of robustness is that under a random permutation from a min-wise independent family, any element of a fixed set has an equal chance to get any rank in the image of the set, not only the minimum as required by definition. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 18–30, 2001