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 |
|---|---|---|
2007 | 10.1007/978-3-540-75225-7_13 | ALT |
Keywords | Field | DocType |
parameterized learnability,related problems,pac model,complete problem,improper equivalence query,parameterized complexity,general result,computational complexity,learning theory | Parameterized complexity,Learning theory,Computer science,Oracle,Theoretical computer science,Equivalence (measure theory),Artificial intelligence,Learnability,Machine learning,Computational complexity theory | Conference |
Volume | ISSN | Citations |
4754 | 0302-9743 | 3 |
PageRank | References | Authors |
0.45 | 20 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vikraman Arvind | 1 | 296 | 38.18 |
| Johannes Köbler | 2 | 580 | 46.51 |
| Wolfgang Lindner | 3 | 70 | 7.89 |