>>> Complexity Seminar のお知らせ <<< 

題目： On the Sample Size of k-Min-Wise Independent Permutations
       and Other k-Wise Distributions
発表： 伊東 利哉（東工大，学術国際情報センター）

日時：２００２年９月２０（金）４時３０分〜
場所：東京工業大学 西８ (W) 号館（１０階）コラボレーションルーム
      渡辺 治（内 2688）

(Joint work with Yoshinori Takei, and Jun Tarui)

Abstract: 
An explicit study of min-wise independent permutation families, 
together with variants -- k-restricted, approximate, etc -- was 
initiated by Broder, Charikar, Frieze, and Mitzenmacher [Min-Wise 
Independent Permutations, Proc. STOC, pp.327--336, 1998], and active 
research has ensued. We give a lower bound for the size of 
k-restricted min-wise (exaclty) independent permutation family. 
A family F of permutations of {0,1,...,n-1} is k-restricted min-wise 
independent if for any set X \subseteq {0,1,....,n-1} with |X| \leq k 
and any x \in X, Pr[ \pi(x)= min {\pi(X)}] = 1/|X| when a permutation 
\pi is randomly drawn from F. For the minimum size of a k-restricted 
min-wise independent family, upper bounds of O(n^k) for fixed k have 
been shown: The size \sum_{j\leq k} j{n\choose j} suffices when a 
biased probability ditribution is allowed [Broder-et-al above]; and 
the size q(n)^k lcm(k-1,k-2,....,2), where q(n) is the least prime 
power not smaller than n, suffices for a multiset with the uniform 
distribution [Itoh, Takei, and Tarui, Proc. SODA, pp.137--146, 2000]. 

We show that if a permutation family F of an n-set is k-restricted 
min-wise independent, then $|F| \geq m(n-1,k-1), where 

  m(n,d) = \sum_{i=0}^{d/2}{n \choose i} if d is even, 
  m(n,d) = \sum_{i=0}^{(d-1)/2}{n \choose i} 
                 + {n-1\choose (d-1)/2} if d is odd.

The lower bound for the size of F still holds when we allow an 
aribitrary probability distribution on F.

It is well known [Alon, Spencer, and Erdos: The Probabilistic Method] 
that if random variables X_1,X_2,....,X_n: \Omega \rightarrow {0,1} 
are d-wise independent and Pr[X_i = 1] = p_i is neither 0 nor 1, then
|\Omega| \geq m(n,d). We give the following generalization and derive 
the result above. Say that 0-1 random variables Y_1,\ldots,Y_n are 
fully distributed if for any (e_1,....,e_n) \in {0,1}^n, 
Pr[Y_1=e_1,....,Y_n=e_n] is nonzero. We prove that if random variables
X_1,....,X_n: \Omega \rightarrow {0,1} have an identical d-wise 
distribution with some fully distributed random variables
Y_1,....,Y_n, then |\Omega| \geq m(n,d). The existence of such Y_i's 
is immediate when, as in the case for d-wise independent variables,
one starts with fully-distributed truly random variables and cosiders 
random variables with an identical d-wise distribution.

Our proof is based on linear-algebraic arguments, and once we put the 
problem in an appropriate perspective, simple arguments suffice to show
the linear independence and finish the proof.

以上．