Vector Analysis of Threshold Functions

Viewing n-variable Boolean functions as vectors in R 2 n, we invoke basic tools from linear algebra and linear programming to derive new results on the realizability of Boolean functions using threshold gates. Using this approach, we obtain: (1) a lower bound on the number of input functions required by a threshold gate implementing a given function; (2) a lower bound on the error incurred when a Boolean function is approximated by a linear combination of a set of functions; (3) a limit on the effectiveness of a well known lower-hound technique (based on computing correlations among Boolean functions) for the depth of threshold circuits implementing Boolean functions; (4) a construction showing that every Boolean function ƒ of n input variables is a threshold function of polynomially many input functions, none of which is significantly correlated with ƒ; (5) generalizations of some known results on threshold-circuit complexity, particularly those that are based on spectral analysis.

Authors

• V. Roychowdhury
• K.Y. Siu
• A. Orlitsky
• T. Kailath

Keywords

No keywords are indexed for this paper.