Publications [#236907] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH, ON THRESHOLD CIRCUITS AND POLYNOMIAL COMPUTATION., undefined (January, 1987), pp. 118-123 [pdf]
   (last updated on 2026/02/08)

   Abstract:
   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)).