Logarithmic Depth Circuits for Algebraic Functions

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 Ω (log n)². 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 nO(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 nO(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).