О мультипликативной сложности многочленов

В работе оценивается мультипликативная (нескалярная) сложность $\mu(M_{d,n})$ вычисления класса $M_{d,n}$ комплексных многочленов $n$ переменных степени не выше $d$. Установлено, что при постоянном $d \ge 2$ справедливо соотношение $\mu(M_{d,n}) \asymp n^{\lceil d/2\rceil}$: новой является нижняя оц... View More