Fast Parallel Computation of Polynomials Using Few Processors

Authors:
  • LVL. G. Valiant
    L. G. Valiant
  • SSS. Skyum
    S. Skyum
  • SBS. Berkowitz
    S. Berkowitz
  • CRC. Rackoff
    C. Rackoff

Abstract
It is shown that any multivariate polynomial of degree d that can be computed sequentially in C steps can be computed in parallel in $O((\log d)(\log C + \log d))$ steps using only $(Cd)^{O(1)} $ processors.