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.