Logarithmic Depth Circuits for Algebraic Functions. Revision

摘要

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) to the second power. 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 sub o(1) polynomials, the symmetric functions, as well as division and interpolation of real polynomials. Also described as o(log n) depth algebraic circuits which given as input the first n coefficients of a power series (over an appropriate ring) compute the product of n sub 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(loglog n)) which given n-bit binary numbers, compute the product of n numbers and integer division.