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

発表：武井 由智
      東京工業大学

題目： Construction of Exactly Min-Wise Independent Permutation Families
       
日時：１９９９年３月９日（火）３時３０分〜５時３０分
場所：東京工業大学　西８号館（１１階）
      ＊１０階の渡辺の部屋にまずおいで下さい．

内容：

大規模な文書類似判定問題を背景に，"Min-Wise Independency" なる概念が 
[n]={1,...,n} 上の置換の族 S_n の部分族に対して，最近定義された．
S_n の部分集合 F から置換 \pi をランダムかつ一様にとったとき，任意の 
[n] の部分集合 X および各 x \in X に対し，
  Prob     [\pi(x) = min \pi(X)] = 1/card(X)
\pi \in F 
が成立するとき，F は Exactly Min-Wise Independent Permutation Family
とよばれる．このような F にたいして，lcm(n,n-1,...,1) が card(F) の
下界であることが知られていた．(lcm は最小公倍数)

本発表では，この下界を達成する置換族を具体的に構成するとともに，その
置換族からの多項式時間サンプリングアルゴリズムを示す．また，その構成
を一般化し，任意の Exactly Min-Wise Independent Permutation Family に
対する構成戦略を考える．

（伊東利哉先生，篠崎隆宏氏との共同研究）