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.
We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at firstname.lastname@example.org