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.