Title of article :
Min-wise independent groups
Author/Authors :
Franchi، نويسنده , , C. and Vsemirnov، نويسنده , , M.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2003
Pages :
21
From page :
855
To page :
875
Abstract :
Let Ω be a finite set of cardinality n with a linear order on it and let k be a positive integer. Let F be a set of permutations on Ω and let PrF be an arbitrary distribution of probability on F. The set F is said to be biased k-restricted min-wise independent if for every subset X of Ω such that |X|≤k, and every x∈X, when π is chosen at random in F, we have thatPrF(minπ(X)=π(x))=1|X|.We study biased k-restricted min-wise independent groups. In particular, we prove that when k is close to n, then biased k-restricted min-wise independent groups are transitive.
Journal title :
European Journal of Combinatorics
Serial Year :
2003
Journal title :
European Journal of Combinatorics
Record number :
1550006
Link To Document :
بازگشت