Volume 7 (2011)
Article 13 pp. 185-188
[Note]

Computing Polynomials with Few Multiplications

Received: June 19, 2011

Published: September 16, 2011

Published: September 16, 2011

**Keywords:**arithmetic circuits, multiplications, Polynomial Identity Testing

**Categories:**note, complexity theory, circuit complexity, arithmetic circuits, multiplication, polynomials - multivariate, 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.