Min-wise independent permutations (extended abstract)
Andrei Broder, Moses Charikar, ALAN M. FRIEZE, Michael Mitzenmacher · 1998
We define and study the notion of min-wise independent families of permutations.We say that F ⊆ S n is min-wise independent if for any set X ⊆ [n] and any x ∈ X, when π is chosen at random in F we have Pr min{π(X)} = π(x) = 1 |X| .