Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45749
Title: ON THE FOURIER SPECTRUM OF MONOTONE FUNCTIONS
Authors: Bshouty, N.
Tamon, T.
Keywords: Computer Science
Issue Date: 1-Apr-1995
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.
URI: http://hdl.handle.net/1880/45749
Appears in Collections:Bshouty, Nader

Files in This Item:
File Description SizeFormat 
1995-554-6.pdf249.32 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.