Theory of Computing ------------------- Title : Computing Polynomials with Few Multiplications Authors : Shachar Lovett Volume : 7 Number : 13 Pages : 185-188 URL : https://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.