ON SOME PROPERTIES OF MIN-WISE INDEPENDENT FAMILIES AND GROUPS OF PERMUTATIONS

    loading  Checking for direct PDF access through Ovid

Abstract

Informally, a family γ ⊆ of permutations is k-restricted min-wise independent if for any X ⊆ [n] with |X| ≤ with |X| ≤ k, each x ∈ X has an equal chance of being mapped to the minimum among π(X). In the second section of this paper, the connection of min-wise independent families of permutations and independence on lth minimum is studied. In the third section, we present a method of constructing a (k + 1)-restricted min-wise independent family from a k-restricted min-wise independent family when k is odd. As a corollary, we improve the existing upper bound on the minimum size of a 4-restricted min-wise independent family. In the last section, we consider min-wise independent groups of permutations. Bibliography: 12 titles.

Related Topics

    loading  Loading Related Articles