Harmonic Analysis of Polynomial Threshold Functions
Jehoshua Bruck · SIAM Journal on Discrete Mathematics · 1990
The analysis of linear threshold Boolean functions has recently attracted the attention of those interested in circuit complexity as well as of those interested in neural networks. Here a generalization of linear threshold functions is defined, namely, polynomial threshold functions, and its relation to the class of linear threshold functions is investigated. A Boolean function is polynomial threshold if it can be represented as a sign function of a polynomial that consists of a polynomial (in the number of variables) number of terms. The main result of this paper is showing that the class of polynomial threshold functions (which is called $PT_1 $) is strictly contained in the class of Boolean functions that can be computed by a depth 2, unbounded fan-in polynomial size circuit of linear threshold gates (which is called $LT_2 $). Harmonic analysis of Boolean functions is used to derive a necessary and sufficient condition for a function to be an S-threshold function for a given set S of monomials. This condition is used to show that the number of different S-threshold functions, for a given S, is at most $2^{( n + 1 )| S |}$. Based on the necessary and sufficient condition, a lower bound is derived on the number of terms in a threshold function. The lower bound is expressed in terms of the spectral representation of a Boolean function. It is found that Boolean functions having an exponentially small spectrum are not polynomial threshold. A family of functions is exhibited that has an exponentially small spectrum; they are called “semibent” functions. A function is constructed that is both semibent and symmetric to prove that $PT_1 $ is properly contained in $LT_2 $.