On threshold circuits and polynomial computation

Publication ,  Journal Article
Reif, JH; Tate, SR
Published in: SIAM Journal on Computing
January 1, 1992

A Threshold Circuit consists of an acyclic digraph of unbounded fanin, where each node computes a threshold function or its negation. This paper investigates the computational power of Threshold Circuits. A surprising relationship is uncovered between Threshold Circuits and another class of unbounded fanin circuits which are denoted Finite Field ZP(n) Circuits, where each node computes either multiple sums or products of integers modulo a prime P(n). In particular, it is proved that all functions computed by Threshold Circuits of size S(n) ≥ n and depth D(n) can also be computed by ZP(n) Circuits of size O(S(n) log S(n) + nP(n) log P(n) and depth O(D(n)). Furthermore, it is shown that all functions computed by ZP(n) Circuits of size S(n) and depth D(n) can be computed by Threshold Circuits of size O(1/ε2) (S(n) log P(n))1+ε and depth O((1/ε5)D(n)). These are the main results of this paper. There are many useful and quite surprising consequences of this result. For example, an integer reciprocal can be computed in size nO(1) and depth O(1). More generally, any analytic function with a convergent rational polynomial power series (such as sine, cosine, exponentiation, square root, and logarithm) can be computed within accuracy 2-n(c), for any constant c, by Threshold Circuits of polynomial size and constant depth. In addition, integer and polynomial division, FFT, polynomial interpolation, Chinese Remaindering, all the elementary symmetric functions, banded matrix inverse, and triangular Toeplitz matrix inverse can be exactly computed by Threshold Circuits of polynomial size and constant depth. All these results and simulations hold for polytime uniform circuits. This paper also gives a corresponding simulation of logspace uniform ZP(n) Circuits by logspace uniform Threshold Circuits requiring an additional multiplying factor of O(log log log P(n)) depth. Finally, purely algebraic methods for lower bounds for ZP(n) Circuits are developed. Using degree arguments. a Depth Hierarchy Theorem for ZP(n) Circuits is proved: for any S(n) ≥ n, D(n) = O(S(n)c′) for some constant c′ < 1, and prime P(n) where 6(S(n)/D(n))D(n) < P(n) ≤ 2n, there exist explicitly constructible functions computable by ZP(n) Circuits of size S(n) and depth D(n), but provably not computable by ZP(n) Circuits of size S(n)c and depth o(D(n)) for any constant c ≥ 1.

Published In

SIAM Journal on Computing

0097-5397

January 1, 1992

21

5

Start / End Page

896 / 908

• Computation Theory & Mathematics
• 4903 Numerical and computational mathematics
• 4901 Applied mathematics
• 4613 Theory of computation
• 0802 Computation Theory and Mathematics
• 0101 Pure Mathematics

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Tate, S. R. (1992). On threshold circuits and polynomial computation. SIAM Journal on Computing, 21(5), 896–908. https://doi.org/10.1137/0221053
Reif, J. H., and S. R. Tate. “On threshold circuits and polynomial computation.” SIAM Journal on Computing 21, no. 5 (January 1, 1992): 896–908. https://doi.org/10.1137/0221053.
Reif JH, Tate SR. On threshold circuits and polynomial computation. SIAM Journal on Computing. 1992 Jan 1;21(5):896–908.
Reif, J. H., and S. R. Tate. “On threshold circuits and polynomial computation.” SIAM Journal on Computing, vol. 21, no. 5, Jan. 1992, pp. 896–908. Scopus, doi:10.1137/0221053.
Reif JH, Tate SR. On threshold circuits and polynomial computation. SIAM Journal on Computing. 1992 Jan 1;21(5):896–908.

Published In

SIAM Journal on Computing

0097-5397

January 1, 1992

21

5

896 / 908