ON THE FOURIER SPECTRUM OF MONOTONE FUNCTIONS
| dc.contributor.author | Bshouty, N. | eng |
| dc.contributor.author | Tamon, T. | eng |
| dc.date.accessioned | 2008-02-27T16:49:32Z | |
| dc.date.available | 2008-02-27T16:49:32Z | |
| dc.date.computerscience | 1999-05-27 | eng |
| dc.date.issued | 1995-04-01 | eng |
| dc.description.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. | eng |
| dc.description.notes | 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 digitize@ucalgary.ca | eng |
| dc.identifier.department | 1995-554-6 | eng |
| dc.identifier.doi | http://dx.doi.org/10.11575/PRISM/30485 | |
| dc.identifier.uri | http://hdl.handle.net/1880/45749 | |
| dc.language.iso | Eng | eng |
| dc.publisher.corporate | University of Calgary | eng |
| dc.publisher.faculty | Science | eng |
| dc.subject | Computer Science | eng |
| dc.title | ON THE FOURIER SPECTRUM OF MONOTONE FUNCTIONS | eng |
| dc.type | unknown | |
| thesis.degree.discipline | Computer Science | eng |
Files
License bundle
1 - 1 of 1