| Presentation | 2006-03-23 Improved Lower Bounds for Families of ε-Approximate k-Restricted Min-Wise Independent Permutations Toshiya ITOH, Tatsuya NAGATANI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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]. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Min-Wise Independence / Positive Definite / Ramsey Number / Linear Algebra Method |
| Paper # | COMP2005-66 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2006/3/16(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Improved Lower Bounds for Families of ε-Approximate k-Restricted Min-Wise Independent Permutations |
| Sub Title (in English) | |
| Keyword(1) | Min-Wise Independence |
| Keyword(2) | Positive Definite |
| Keyword(3) | Ramsey Number |
| Keyword(4) | Linear Algebra Method |
| 1st Author's Name | Toshiya ITOH |
| 1st Author's Affiliation | GSIC, Tokyo Inst. of Tech.() |
| 2nd Author's Name | Tatsuya NAGATANI |
| 2nd Author's Affiliation | Dept. of Inform. Proc., Tokyo Inst. of Tech. |
| Date | 2006-03-23 |
| Paper # | COMP2005-66 |
| Volume (vol) | vol.105 |
| Number (no) | 680 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |