# ON THRESHOLD CIRCUITS AND POLYNOMIAL COMPUTATION.

Published

Journal Article

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 Authors

### Cited Authors

- Reif, JH

### Published Date

- January 1, 1987

### Start / End Page

- 118 - 123

### Citation Source

- Scopus