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 trade-offs for threshold circuits that compute the parity function. Using a fundamental result in the theory of rational approximation, we show how to approximate small threshold circuits by rational functions of low degree. We apply this result to establish an almost optimal lower bound of Ω(n 2/ln2 n) on the number of edges of any depth-2 threshold circuit with polynomially bounded weights that computes the parity function. We also prove that any depth-3 threshold circuit with polynomially bounded weights requires Ω(n 1. 2/ln5/3 n) edges to compute parity. On the other hand, we give a construction of a depth d threshold circuit that computes parity with n 1+1/Θ(φ d ) edges where φ = (1 + √5)/2 is the golden ratio. We conjecture that there are no linear size bounded depth threshold circuits for computing parity.

Authors

• R. Paturi
• M.E. Saks

Keywords

No keywords are indexed for this paper.