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)