ON THRESHOLD CIRCUITS AND POLYNOMIAL COMPUTATION.

The author investigates the computational power of threshold circuits. He discovers a relationship with another class of unbounded fan-in circuits which he denotes finite field Z//P//(//n//) circuits, where each node computes either multiple sums or products of integers modulo a prime P(n). In particular, he proves that all functions computed by threshold circuits of size S(n) greater than equivalent to n and depth D(n) can also be computed by Z//P//(//n//) circuits of size O(S(n) plus nP(n)) and depth O(D(n)). Furthermore, he proves that all functions computed by Z//P//(//n//) circuits of size S(n) and depth D(n) can be computed by threshold circuits of size (S(n)logP(n))**O**(**1**) and depth O(D(n)).

Duke Scholars

Author John H. Reif Computer Science