Logarithmic Depth Circuits for Algebraic Functions
John H. Reif · SIAM Journal on Computing · 1986
This paper describes 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 $. Algebraic circuits assume unit cost for elemental addition and multiplication. This paper describes $O(\log n)$ depth algebraic circuits which given as input the coefficients of n degree polynomials (over an appropriate ring), compute the product of $n^{O(1)} $ polynomials, the symmetric functions, as well as division and interpolation of real polynomials. Also described are $O(\log n)$ depth algebraic circuits which are given as input the first n coefficients of a power series (over an appropriate ring) compute the product of $n^{O(1)} $ power series, as well as division, reciprocal and reversion of real power series. 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^{ - n} $, 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)$.