ML Anthology

Parameterized Learnability of K -Juntas and Related Problems

Vikraman Arvind, Johannes Köbler, Wolfgang Lindner
ALT 2007 pp. 120-134
doi:10.1007/978-3-540-75225-7_13 /alt/2007/arvind2007alt-parameterized/

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.

PDF ALT Semantic Scholar

Cite

Text

Arvind et al. "Parameterized Learnability of K -Juntas and Related Problems." International Conference on Algorithmic Learning Theory, 2007. doi:10.1007/978-3-540-75225-7_13

Markdown

[Arvind et al. "Parameterized Learnability of K -Juntas and Related Problems." International Conference on Algorithmic Learning Theory, 2007.](https://mlanthology.org/alt/2007/arvind2007alt-parameterized/) doi:10.1007/978-3-540-75225-7_13

BibTeX

@inproceedings{arvind2007alt-parameterized,
  title     = {{Parameterized Learnability of K -Juntas and Related Problems}},
  author    = {Arvind, Vikraman and Köbler, Johannes and Lindner, Wolfgang},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2007},
  pages     = {120-134},
  doi       = {10.1007/978-3-540-75225-7_13},
  url       = {https://mlanthology.org/alt/2007/arvind2007alt-parameterized/}
}