Browsing by Author "Tamon, T."
Now showing 1 - 1 of 1
Results Per Page
Sort Options
Item Open Access ON THE FOURIER SPECTRUM OF MONOTONE FUNCTIONS(1995-04-01) Bshouty, N.; Tamon, T.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.