ON THE FOURIER SPECTRUM OF MONOTONE FUNCTIONS
Date
1995-04-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We study the Fourier spectrum of monotone boolean functions. Our
main result is that any monotone boolean function of n inputs has
most of its power spectrum on the coefficients of "degree" soft-Oh
of square-root of n under any product distribution. As a consequence,
we derive a subexponential PAC learning algorithm over product
distributions and a subexponential size, sublinear depth non-monotone
circuit approximation for unrestricted monotone boolean functions.
Our other results include a new measure of complexity for distributions,
called convex dimension, and several efficient PAC learning algorithms
for subclasses of monotone boolean functions.
Description
Keywords
Computer Science