Theory of Computing
-------------------
Title : Computing Polynomials with Few Multiplications
Authors : Shachar Lovett
Volume : 7
Number : 13
Pages : 185-188
URL : http://www.theoryofcomputing.org/articles/v007a013
Abstract
--------
It 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(sqrt{{n+d choose d}}), 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{{n+d choose d}}.(nd)^{O(1)} multiplication gates suffice.