Publications [#237102] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH, LOGARITHMIC DEPTH CIRCUITS FOR ALGEBRAIC FUNCTIONS., SIAM Journal on Computing, vol. 15 no. 1 (January, 1986), pp. 231-242, Society for Industrial & Applied Mathematics (SIAM) [doi]
   (last updated on 2026/01/14)

   Abstract:
   This paper describes parallel circuits for computation of a large class of algebraic functions on polynomials, power series, and integers, for which, it has been a long standing open problem to compute in depth less than OMEGA (log n)**2. Furthermore this paper describes boolean circuits of depth O(log n(log log n)) which, given n-bit binary numbers, compute the product of n numbers and integer division. As corollaries, we get boolean circuits of the same depth for evaluating, within accuracy 2** minus **2, polynomials, power series, and elementary functions such as (fixed) powers, roots, exponentiations, logarithm, sine and cosine. All these circuits have constant indegree, polynomial size, and may be uniformly constructed by a deterministic Turing machine with space O(log n).