Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-094 | 20th June 2011 03:32

Computing polynomials with few multiplications

RSS-Feed




TR11-094
Authors: Shachar Lovett
Publication: 20th June 2011 09:16
Downloads: 3778
Keywords: 


Abstract:

A 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.



ISSN 1433-8092 | Imprint