Please use this identifier to cite or link to this item:
|Title:||ON THE FOURIER SPECTRUM OF MONOTONE FUNCTIONS|
|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.|
|Appears in Collections:||Bshouty, Nader |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.