Journal of the Association for Computing Machinery, Vol. 43, No. 4, July 1996, pp. 747–770.

On the Fourier Spectrum of Monotone Functions

NADER H. BSHOUTY

AND

CHRISTINO TAMON

Abstract. In this paper, monotone Boolean functions are studies using harmonic analysis on the cube. The main result is that any monotone Boolean function has most of its power spectrum on its Fourier coefficients of “degree” at most O(\sqrt{n}) under any product distribution. This is similar to a result of Linial et al. [1993], which showed that AC^{0} functions have almost all of their power spectrum on the coefficients of degree, at most (log n)^{O(1)}, under the uniform distribution. As a consequence of the main result, the following two corollaries are obtained:

• For any ϵ > 0, monotone Boolean functions are PAC learnable with error ϵ under product distributions in time 2^{Õ((1/ϵ)\sqrt{n})}.

• Any monotone Boolean function can be approximated within error ϵ under product distributions by a non-monotone Boolean circuit of size 2^{Õ(1/ϵ\sqrt{n})} and depth Õ(1/ϵ\sqrt{n}).

The learning algorithms runs in time subexponential as long as the required error is Ω(1/(\sqrt{n} log n)). It is shown that this is tight in the sense that for any subexponential time algorithm there is a monotone Boolean function for which this algorithm cannot approximate with error better than Õ(1/\sqrt{n}).

The main result is also applied to other programs in learning and complexity theory. In learning theory, several polynomial-time algorithms for learning some classes of monotone Boolean functions, such as Boolean functions with O(log^{2} n/ log log n) relevant variables, are presented. In complexity theory, some questions regarding monotone NP-complete problems are addressed.

Categories and Subject Descriptors. F.1.2 [Computation by Abstract Devices]: Modes of Computation—probabilistic computation; F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems—computation of transforms; computation on polynomials; G.3 [Probability and Statistics]—probabilistic algorithms; I.2.6 [Artificial Intelligence]: Learning—concept learning

General Terms. Algorithms, Theory

Additional Key words and Phrases. Approximation, circuits, complexity, Fourier transform, functions, harmonic analysis learning, monotone Boolean, monotone circuits

Copyright 1996 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.