| Presentation | 2002/7/29 On the Influence of Outliers in the Support Vector Machine Framework(1) Jin-Yi CAI, Osamu WATANABE, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | For showing collapsing relativized results, we propose to restrict Oracle queries to "stringent" ones; when simulating one machine Q_2 of some type by a machine Q_1 of another type, the simulating machine Q_1 does not query strings that are longer than a specified query length bound for the simulated machine Q_2. Under such stringent oracle access, we show, for example, some oracle A such that NP(A) = BPP(A). Similar results hold for the relation between P and for classes in PH. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | P vs. NP conjecture / relativization / stringent oracle access / switching lemma / the polynomial-time |
| Paper # | COMP2002-23 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2002/7/29(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) | On the Influence of Outliers in the Support Vector Machine Framework(1) |
| Sub Title (in English) | |
| Keyword(1) | P vs. NP conjecture |
| Keyword(2) | relativization |
| Keyword(3) | stringent oracle access |
| Keyword(4) | switching lemma |
| Keyword(5) | the polynomial-time |
| 1st Author's Name | Jin-Yi CAI |
| 1st Author's Affiliation | Computer Sciences Dept., Univ.() |
| 2nd Author's Name | Osamu WATANABE |
| 2nd Author's Affiliation | Dept. Math. and Comp. Sci Tokyo Inst. of Tech. |
| Date | 2002/7/29 |
| Paper # | COMP2002-23 |
| Volume (vol) | vol.102 |
| Number (no) | 258 |
| Page | pp.pp.- |
| #Pages | 5 |
| Date of Issue | |