ECCC-Report TR11-094https://eccc.weizmann.ac.il/report/2011/094Comments and Revisions published for TR11-094en-usMon, 20 Jun 2011 09:16:52 +0300
Paper TR11-094
| Computing polynomials with few multiplications |
Shachar Lovett
https://eccc.weizmann.ac.il/report/2011/094A folklore result in arithmetic complexity shows that the number of multiplications required to compute some $n$-variate polynomial of degree $d$ is $\sqrt{{n+d \choose n}}$. We complement this by an almost matching upper bound, showing that any $n$-variate polynomial of degree $d$ over any field can be computed with only $\sqrt{{n+d \choose n}} \cdot (nd)^{O(1)}$ multiplications.
Mon, 20 Jun 2011 09:16:52 +0300https://eccc.weizmann.ac.il/report/2011/094