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.
Licensed under a Creative Commons Attribution License (CC-BY)