Presentation | 2002/10/17 On Property Testing Algorithms for Monotone Boolean Formulae Kazuyuki AMANO, Akira MARUOKA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | We consider the problem of determining whether a given function &inof; : {0, 1}^n → {0, 1} belongs to a certain class of Boolean functions Fp or whether it is far from the class. More precisely, given query access to the function &inof; and given a distance parameter ε, we would like to decide whether &inof; ⋴ Fp or whether it differs from every g ⋴ Fp on more than an ε fraction of the inputs. We give algorithms for testing monomials whose query complexity is O(1/ε^2) and for testing monotone DNF formulae with at most I terms whose query complexity is O(l^3/ε^2) |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Property testing / Monomial / Disjunctive normal form / Computational learning theory / Fourier analysis |
Paper # | COMP2002-41 |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 2002/10/17(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 | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | On Property Testing Algorithms for Monotone Boolean Formulae |
Sub Title (in English) | |
Keyword(1) | Property testing |
Keyword(2) | Monomial |
Keyword(3) | Disjunctive normal form |
Keyword(4) | Computational learning theory |
Keyword(5) | Fourier analysis |
1st Author's Name | Kazuyuki AMANO |
1st Author's Affiliation | GSIS, Tohoku University() |
2nd Author's Name | Akira MARUOKA |
2nd Author's Affiliation | GSIS, Tohoku University |
Date | 2002/10/17 |
Paper # | COMP2002-41 |
Volume (vol) | vol.102 |
Number (no) | 396 |
Page | pp.pp.- |
#Pages | 7 |
Date of Issue |