Volume 7 (2011) Article 13 pp. 185-188 [Note]
Computing Polynomials with Few Multiplications
Received: June 19, 2011
Published: September 16, 2011
Is is a folklore result in arithmetic complexity that the number of multiplication gates required to compute a worst-case $n$-variate polynomial of degree $d$ is at least
$\Omega \left( \sqrt{\binom{n+d}{d}} \right)$,
even if addition gates are allowed to compute arbitrary linear combinations of their inputs. In this note we complement this by an almost matching upper bound, showing that for any $n$-variate polynomial of degree $d$ over any field,
$\sqrt{\binom{n+d}{d}} \cdot (nd)^{O(1)}$