A Geometric Approach to Threshold Circuit Complexity

Abstract

We introduce a geometric approach for investigating the power of threshold circuits. Viewing n-variable boolean functions as vectors in R 2n , we invoke 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) upper-bounds on the number of spurious memories in Hopfield networks, and on the number of functions implementable by a depth-d threshold circuit; (2) a lower bound on the number of orthogonal input functions required to implement a threshold function; (3) a necessary condition for an arbitrary set of input functions to implement a threshold function; (4) a lower bound on the error incurred in approximating boolean functions using sparse polynomials; (5) a limit on the effectiveness of the only known lower-bound technique (based on computing correlations among boolean functions) for the depth of threshold circuits implementing boolean functions, and (6) a constructive proof that every boolean function f of n input variables is a threshold function of polynomially many input functions, none of which is significantly correlated with f. Some of these results lead to generalizations of key results concerning threshold circuit complexity, particularly those that are based on the so-called spectral or Harmonic analysis approach. Moreover, our geometric approach yields simple proofs, based on elementary results from linear algebra, for many of these earlier results.