Bruck, Jehoshua and Smolensky, Roman (1990) Polynomial Threshold Functions, AC^0 Functions and Spectral Norms. In: 1990 31st Annual Symposium on Foundations of Computer Science, Proceedings. IEEE Computer Society Press , Los Alamitos, CA, pp. 632-641. ISBN 0-8186-2082-X http://resolver.caltech.edu/CaltechAUTHORS:20120425-065829076
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120425-065829076
The class of polynomial-threshold functions is studied using harmonic analysis, and the results are used to derive lower bounds related to AC^0 functions. A Boolean function is polynomial threshold if it can be represented as a sign function of a sparse polynomial (one that consists of a polynomial number of terms). The main result is that polynomial-threshold functions can be characterized by means of their spectral representation. In particular, it is proved that a Boolean function whose L_1 spectral norm is bounded by a polynomial in n is a polynomial-threshold function, and that a Boolean function whose L_∞^(-1) spectral norm is not bounded by a polynomial in n is not a polynomial-threshold function. Some results for AC^0 functions are derived.
|Item Type:||Book Section|
|Additional Information:||© 1990 IEEE. Date of Current Version: 06 August 2002. We thank Noga Alon for his useful observations that greatly improved this paper and to Chaim Gotsman and Sunny Siu for their comments on an early draft of this paper.|
|Other Numbering System:|
|Official Citation:||Bruck, J.; Smolensky, R.; , "Polynomial threshold functions, AC functions and spectrum norms," Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on , vol., no., pp.632-641 vol.2, 22-24 Oct 1990 doi: 10.1109/FSCS.1990.89585 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=89585&isnumber=2915|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Ruth Sustaita|
|Deposited On:||25 Apr 2012 17:15|
|Last Modified:||26 Dec 2012 15:08|
Repository Staff Only: item control page