| 講演名 | 2006-03-23 ε-近似k-制限最小値独立置換族のサイズの下界 伊東 利哉, 永谷 達也, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 最小値独立置換族(とその拡張概念であるε-近似k-制限最小値独立置換族)は,インターネット上に存在する類似した文書の特定に有用であることが知られており,それらの構成法,置換族のサイズに関する(非)構成的上界・下界が数多く示されている.任意の整数n>0に対し,集合[numerical formula]上の置換全体の集合をS_nとするとき,置換族F⊆S_nがε-近似k-制限最小値独立であるとは,任意の(空でない)部分集合[numerical formula]と任意のx∈Xに対し,置換π∈Fを一様且つ無作為に選んだ場合,[numerical formula]が成り立つことを言う(ただし,‖A‖は有限集合Aの要素数を表すものとする).これまでにε-近似k-制限最小値独立置換族F⊆S_nのサイズに関して,以下のことが知られている:(構成的上界)[numerical formula];(非構成的上界)[numerical formula];(下界)[numerical formula],[numerical formula],[numerical formula].本論文では,まず始めに完全グラフの多色枝塗りに関するラムゼー数の上界を評価し,さらに代数的手法を用いることで,より厳密なε-近似k-制限最小値独立置換族F⊆S_nのサイズの下界[numerical formula]を導出する. |
| 抄録(英) | A family F of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. For any integer n>0, let S_n be the family of all permutations on [numerical formula]. For any integer k such that 1≤k≤n and any real ε>0, we say that a family F⊆S_n of permutations is ε-approximate k-restricted min-wise independent if for any (nonempty) subset X⊆[1, n] such that ‖X‖≤k and any element x∈X,[numerical formula], when π is chosen from F uniformly at random (where ‖A‖denotes the cardinality of a finite set A). For the size of families F⊆S_n of ε-approximate k-restricted min-wise independent permutations, the following results are known: For any integer k such that 1≤k≤n and any real ε>0, (constructive upper bound) [numerical formula]; (nonconstructive upper bound) [numerical formula]; (lower bound) [numerical formula] and [numerical formula], [numerical formula]. In this paper, we first derive an upper bound for the Ramsey number of the edge coloring with m≤2 colors of a complete graph K_l of l vertices, and by the linear algebra method, we then derive a slightly improved lower bound, i.e., we show that for any family F⊆S_n of ε-approximate k-restricted min-wise independent permutations, [numerical formula]. |
| キーワード(和) | 最小値独立 / 正定値 / ラムゼー数 / 代数的手法 |
| キーワード(英) | Min-Wise Independence / Positive Definite / Ramsey Number / Linear Algebra Method |
| 資料番号 | COMP2005-66 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2006/3/16(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | ε-近似k-制限最小値独立置換族のサイズの下界 |
| サブタイトル（和） | |
| タイトル（英） | Improved Lower Bounds for Families of ε-Approximate k-Restricted Min-Wise Independent Permutations |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 最小値独立 / Min-Wise Independence |
| キーワード(2)（和/英） | 正定値 / Positive Definite |
| キーワード(3)（和/英） | ラムゼー数 / Ramsey Number |
| キーワード(4)（和/英） | 代数的手法 / Linear Algebra Method |
| 第 1 著者 氏名（和/英） | 伊東 利哉 / Toshiya ITOH |
| 第 1 著者 所属（和/英） | 東京工業大学 学術国際情報センター GSIC, Tokyo Inst. of Tech. |
| 第 2 著者 氏名（和/英） | 永谷 達也 / Tatsuya NAGATANI |
| 第 2 著者 所属（和/英） | 東京工業大学 物理情報システム創造専攻 Dept. of Inform. Proc., Tokyo Inst. of Tech. |
| 発表年月日 | 2006-03-23 |
| 資料番号 | COMP2005-66 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 680 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |