Learning symmetric k-juntas in time n^o(k)

Mihail N. Kolountzakis, Evangelos Markakis, Aranyak Mehta

We give an algorithm for learning symmetric k-juntas (boolean functions of $n$ boolean variables which depend only on an unknown set of $k$ of these variables) in the PAC model und…