Parameterized Learnability of k-Juntas and Related Problems
V. Arvind, J. Köbler, W. Lindner
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: juntas.pdf