Volume 7 (2011) Article 13 pp. 185-188 [Note]
Computing Polynomials with Few Multiplications
Received: June 19, 2011
Published: September 16, 2011
Download article from ToC site:
[PDF (166K)]    [PS (429K)]    [PS.GZ (169K)]
[Source ZIP]
Keywords: arithmetic circuits, multiplications, polynomial identity testing
ACM Classification: F.1.3
AMS Classification: 68Q25

Abstract: [Plain Text Version]

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)}$
multiplication gates suffice.