%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "bshoutyt96.ltx",
%%%     date      = "27 September 1996",
%%%     time      = "14:44:18 EDT",
%%%     author    = "David M. Jones",
%%%     email     = "jacm@theory.lcs.mit.edu",
%%%     url       = "http://theory.lcs.mit.edu/~jacm/",
%%%     address   = "Journal of the ACM
%%%                  MIT Laboratory for Computer Science
%%%                  Room NE43-316
%%%                  545 Technology Square
%%%                  Cambridge, MA 02139
%%%                  USA",
%%%     telephone = "(617) 253-5936",
%%%     FAX       = "(617) 253-3480",
%%%     checksum  = "08150 126 573 4883",
%%%     codetable = "ISO/ASCII",
%%%     supported = "yes",
%%%     docstring = "Copyright (c) 1995 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.
%%%
%%%                  This is a LaTeX2e file.  To process it, you will
%%%                  need a copy of the acmabs document class, which is
%%%                  available via the following URL:
%%%
%%%                  http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%%                  ",
%%%  }
%%% ====================================================================

\documentclass{acmabs}

\begin{document}

\Journal{Journal of the ACM}

\refkey{BshoutyT96}

\title{On the {Fourier} Spectrum of Monotone Functions}

\author{Nader~H. Bshouty \and Christino Tamon}

\Pages{747--770}

\Month{July}

\Year{1996}

\Volume{43}

\Number{4}

\maketitle

\begin{abstract}

In this paper, monotone Boolean functions are studies using harmonic
analysis on the cube. The main result is that \emph{any} monotone
Boolean function has most of its power spectrum on its Fourier
coefficients of ``degree'' at most $O(\sqrt{n})$ under \emph{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:
\begin{itemize} \item For any $\epsilon > 0$, monotone Boolean
functions are PAC learnable with error $\epsilon$ under product
distributions in time $2^{\tilde{O}((1/\epsilon)\sqrt{n})}$. \item Any
monotone Boolean function can be approximated within error $\epsilon$
under product distributions by a non-monotone Boolean circuit of size
$2^{\tilde{O}(1/\epsilon\sqrt{n})}$ and depth $\tilde{O}(1/\epsilon
\sqrt{n})$. \end{itemize} The learning algorithms runs in time
subexponential as long as the required error is $\Omega(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
$\tilde{O}(1/\sqrt{n})$. \par 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.

\end{abstract}

\begin{categories}

F.1.2 [\textbf{Computation by Abstract Devices}]: Modes of
Computation---\emph{probabilistic computation}; F.2.1
[\textbf{Analysis of Algorithms and Problem Complexity}]: Numerical
Algorithms and Problems---\emph{computation of transforms\textup;
computation on polynomials}; G.3 [\textbf{Probability and
Statistics}]---\emph{probabilistic algorithms}; I.2.6
[\textbf{Artificial Intelligence}]: Learning---\emph{concept learning}

\end{categories}

\begin{terms}

Algorithms, Theory

\end{terms}

\begin{keywords}

Approximation, circuits, complexity, Fourier transform, functions, harmonic
  analysis learning, monotone Boolean, monotone circuits

\end{keywords}

\end{document}
