| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 437950 | Theoretical Computer Science | 2009 | 9 Pages |
Abstract
We study the parameterized complexity of learning k-juntas and some variations of juntas. We show the hardness of learning k-juntas and subclasses of k-juntas in the PAC model by reductions from a -complete problem. On the other hand, as a consequence of a more general result, we show that k-juntas are exactly learnable with improper equivalence queries and access to a oracle.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
