On the Parallel Evaluation of Multivariate Polynomials
Laurent Hyafil · SIAM Journal on Computing · 1979
We prove that any multivariate polynomial P of degree d that can be computed with $C(P)$ multiplications-divisions can be computed in $O(\log d \cdot \log C(P))$ parallel steps and $O(\log d)$ parallel multiplicative steps.