Name
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 W[2]-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 W[P] oracle. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.tcs.2009.07.003 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Computational complexity,PAC model,complete problem,improper equivalence query,parameterized complexity,Parameterized learnability,Learning theory,general result | Journal | 410 |
Issue | ISSN | Citations |
47-49 | Theoretical Computer Science | 3 |
PageRank | References | Authors |
0.37 | 20 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 52 | 4.34 |
| Johannes Köbler | 2 | 580 | 46.51 |
| Wolfgang Lindner | 3 | 70 | 7.89 |