dasarpmar / lowerbounds-survey

A survey of known lower bounds in arithmetic circuits.
27 stars 15 forks source link

Small clarification in rank methods limitations #33

Open Narfinger opened 4 years ago

Narfinger commented 4 years ago

The polynomials we are interested are linear combinations of polynomials in $\mathcal{B}$. Hence, if we can replace all $b\in\mathcal{B}$ with a polynomial $B$, the linear combinations would still hold, i.e., if $f$ is our polynomial with $\sum_{b\in \mathcal{B}} \alphab b$ it would now be $f=\sum{a\in A} \alpha_a B(a)$. While in this case the tensor-rank polynomial $B(y)$ is linear, the Waring rank polynomial is not.