Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
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)] [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.