####
Completeness and Robustness Properties of Min-Wise Independent Permutations

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.