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

Abstract

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 under the uniform distribution, which runs in time n^{O(k/\log k)}. Our bound is obtained by proving the following result: Every symmetric boolean function on k variables, except for the parity and the constant functions, has a non-zero Fourier coefficient of order at least 1 and at most O(k/\log k). This improves the previously best known bound of (3/31)k, and provides the first n^{o(k)} time algorithm for learning symmetric juntas.