  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.
