APPROXIMATING THRESHOLD CIRCUITS BY RATIONAL FUNCTIONS

Motivated by the problem of understanding the limitations of threshold networks for representing boolean functions, we consider size-depth t rade-offs for threshold circuits that compute the parity function. Usi ng a fundamental result in the theory of rational approximation, we sh ow how to approximate small threshold circuits by rational functions o f low degree. We apply this result to establish an almost optimal lowe r bound of OMEGA(n2/ln2 n) on the number of edges of any depth-2 thres hold circuit with polynomially bounded weights that computes the parit y function. We also prove that any depth-3 threshold circuit with poly nomially bounded weights requires OMEGA(n1.2/ln5/3 n) edges to compute parity. On the other hand, we give a construction of a depth d thresh old circuit that computes parity with n1+1/theta(d)) edges where phi = (1 + square-root 5)/2 is the golden ratio. We conjecture that there a re no linear size bounded depth threshold circuits for computing parit y. (C) 1994 Academic Press, Inc.