On the Fourier spectrum of symmetric boolean functions with applications to learning symmetric juntas

Abstract

We study the following question: What is the smallest t such that every symmetric boolean function on k variables (which is not a constant or a parity function), has a non-zero Fourier coefficient of order at least 1 and at most t? We exclude the constant functions for which there is no such t and the parity functions for which t has to be k. Let τ(k) be the smallest such t. The main contribution of this paper is a proof of the following self similar nature of this question: If τ (l) ≤ s, then for any ε > 0 and for k ≥ k0(l, ε), τ(k) ≤ (s+1/l+1 + ε) k Coupling this result with a computer based search which establishes τ(30) = 2, one obtains that for large enough k, τ(k) ≤ 3k/31. The motivation for our work is to understand the complexity of learning symmetric juntas. A k-junta is a boolean function of n variables that depends only on an unknown subset of k variables. If f is symmetric in the variables it depends on, it is called a symmetric k-junta. Our results imply an algorithm to learn the class of symmetric k-juntas, in the uniform PAC learning model, in time approximately n 3k/31. This improves on a result of Mossel, O'Donnell and Servedio in [11], who show that symmetric k-juntas can be learned in time n 2k/3 (the main result in [11] is much more general, giving a bound of n0.7k for learning juntas). Technically, the study of τ(k) is equivalent to the study of 0/1 solutions of a system of Diophantine equations involving binomial coefficients. As a first step, we simplify these Diophantine equations by moving to a representation of boolean functions, which is equivalent to their Fourier representation, but seems much simpler for the application of number theoretic tools. Once this is done, we reduce these equations modulo carefully chosen prime numbers to get a simpler system of equations which we can analyze. Finally, we combine the information about the equations over the finite fields in a combinatorial manner to deduce the nature of the 0/1 solutions. © 2005 IEEE.