Geodesic
On the multiplicative complexity of polynomials
Diskretnaya Matematika, Tome 34 (2022) no. 3, pp. 85-89.

Voir la notice de l'article provenant de la source Math-Net.Ru

We study the multiplicative (nonscalar) complexity $\mu(M_{d,n})$ for the class $M_{d,n}$ of complex polynomials in $n$ variables of degree at most $d$. It is shown that the relation $\mu(M_{d,n}) \asymp n^{\lceil d/2\rceil}$ holds for any constant $d \ge 2$. The lower bound for odd values of $d$ in this relation is new. For the case of cubic polynomials we prove more accurate bounds $n^2/18 \lesssim \mu(M_{3,n}) \lesssim n^2/4$.
Keywords: arithmetic circuits, multiplicative complexity, polynomials 
@article{DM_2022_34_3_a6,
     author = {I. S. Sergeev},
     title = {On the multiplicative complexity of polynomials},
     journal = {Diskretnaya Matematika},
     pages = {85--89},
     publisher = {mathdoc},
     volume = {34},
     number = {3},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2022_34_3_a6/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - On the multiplicative complexity of polynomials
JO  - Diskretnaya Matematika
PY  - 2022
SP  - 85
EP  - 89
VL  - 34
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2022_34_3_a6/
LA  - ru
ID  - DM_2022_34_3_a6
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T On the multiplicative complexity of polynomials
%J Diskretnaya Matematika
%D 2022
%P 85-89
%V 34
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2022_34_3_a6/
%G ru
%F DM_2022_34_3_a6
I. S. Sergeev. On the multiplicative complexity of polynomials. Diskretnaya Matematika, Tome 34 (2022) no. 3, pp. 85-89. http://geodesic.mathdoc.fr/item/DM_2022_34_3_a6/

[1] Paterson M. S., Stockmeyer L. J., “On the number of nonscalar multiplications necessary to evaluate polynomials”, SIAM J. Comput., 2 (1973), 60–66 | DOI | MR | Zbl

[2] Bürgisser P., Clausen M., Shokrollahi M. A., Algebraic complexity theory, Springer-Verlag, Berlin–Heidelberg, 1997, 646 pp. | MR | Zbl

[3] Chen X., Kayal N., Wigderson A., “Partial derivatives in arithmetic complexity and beyond”, Found. and Trends in Theoret. Comput. Sci., 6:1–2 (2011), 1–138 | MR

[4] Lovett S., “Computing polynomials with few multiplications”, Theory of Computing, 7 (2011), 185–188 | DOI | MR | Zbl

[5] Baur W., Strassen V., “The complexity of partial derivatives”, Theoret. Comput. Sci., 22 (1983), 317–330 | DOI | MR | Zbl

[6] Nechiporuk E. I., “O slozhnosti skhem v nekotorykh bazisakh, soderzhaschikh netrivialnye elementy s nulevymi vesami”, Problemy kibernetiki, 8, Fizmatlit, M., 1962, 123–160 | MR

[7] Mirwald R., Schnorr C. P., “The multiplicative complexity of quadratic Boolean forms”, Theoret. Comput. Sci., 102 (1992), 307–328 | DOI | MR | Zbl