On Threshold Circuits and Polynomial Computation

A Threshold Circuit consists of an acyclic digraph of unbounded fanin, where each node computes a threshold function or its negation. We investigate the computational power of Threshold Circuits. We discover a surprising relationship with another class of unbounded fanin circuits which we denote Finite Field Z<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P(n)</inf> Circuits where each node computes either multiple sums or products of integers modulo a prime P(n). In particular, we prove that all functions computed by Threshold Circuits of size S(n) ≥ n and depth D (n) can be also computed by Z<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P(n)</inf> Circuits of sixe 0(s(<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</inf>) + nP(n)) and depth 0(D(n)). Furthermore, we prove that all functions computed by Z<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P(n)</inf> Circuits of size S(n) and depth D(n) can be computed by Threshold Circuits of sice (S(n)log P(n))0(1) and depth 0(D(n)). This is the main result of this paper. We get many useful and quite surprising consequences of this result. For example, integer reciprocal can be computed in size n0(1) and depth 0(1). More generally, any analytic function with a convergent rational polynomial power series (such as integer reciprocal, sine, cosine, exponentiation, square root, logarithm), can be computed within accuracy 2-nc for any constant c, by Threshold Circuits of polynomial sise and constant depth. Also, integer and polynomial division, FFT, polynomial interpolation, Chinese Remaindering, all the elementary symmetric functions, banded matrix inverses and triangular Toelplits matrix inverse can be exactly computed by Threshold Circuits of polynomial sise and constant depth. All these results and simulations hold for polytime uniform circuits. We give a corresponding simulation of logspace uniform Z<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p(n)</inf> Circuits by logspace uniform Threshold Circuits requiring an additional multiplying factor of 0(logloglog P(n)) depth. We also develop purely algebraic methods for lower bounds for Z<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p(n)</inf> Circuits. Using degree arguments, we prove a Depth Hierarchy Theorem for Z<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p(n)</inf> Circuits: for any S(n) ≥ n, D(n) < S(n)/2 and prime P(n) where 2n ≥ P(n) > 6 (S(n)/D(n))D(n), we can explicitly construct functions computable by Z<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</inf>(n) Circuits of size S(n) and depth D(n), but provably not computable by Z<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</inf>(n) Circuits of sise S(n)c and depth o(D(n)) for any constant c ≥ 1.