A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
This paper examines the class of polynomial threshold functions using harmonic analysis and applies the results to derive lower bounds related to AC0 functions. A Boolean function is polynomial threshold if it can be represented as the sign of a sparse polynomial (one that consists of a polynomial number of teams). The main result of this paper is that the class of polynomial threshold functions can be characterized using their spectral representation. In particular, it is proved that an n-variable Boolean function whose L1 spectral norm is bounded by a polynomial in n is a polynomial threshold function, while a Boolean function whose L10-1 spectral norm is not bounded by a polynomial in n is not a polynomial threshold function [J. Bruck, SIAM J. Discrete Math, 3 (1990), pp. 168-177]. The motivation is that the characterization of polynomial threshold functions can be applied to obtain upper and lower bounds on the complexity of computing with networks of linear threshold elements. In this paper results related to the complexity of computing AC0 functions are presented. More applications of the characterization theorem are presented in [J. Bruck, SIAM J. Discrete Math. 3 (1990), pp. 168-177] and [K.Y. Siu and J. Bruck, SIAM J. Discrete Math, 4 (1991), pp. 423-435].
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
Raymond Wu, Jie Lu
ITA Conference 2007
N.K. Ratha, A.K. Jain, et al.
Workshop CAMP 2000
Leo Liberti, James Ostrowski
Journal of Global Optimization