Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MULTIPLICATIONS:
Reports tagged with multiplications:
TR11-094 | 20th June 2011
Shachar Lovett

#### Computing polynomials with few multiplications

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

ISSN 1433-8092 | Imprint