Geodesic
On the multiplicative complexity of some Boolean functions
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 4, pp. 730-736 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper, we study the multiplicative complexity of Boolean functions. The multiplicative complexity of a Boolean function $f$ is the smallest number of $\&$-gates in circuits in the basis $\{x\& y, x\oplus y, 1\}$ such that each such circuit computes the function $f$. We consider Boolean functions which are represented in the form $x_1, x_2\dots x_n\oplus q(x_1,\dots,x_n)$, where the degree of the function $q(x_1,\dots,x_n)$ is $2$. We prove that the multiplicative complexity of each such function is equal to $(n-1)$. We also prove that the multiplicative complexity of Boolean functions which are represented in the form $x_1\dots x_n\oplus r(x_1,\dots,x_n)$, where $r(x_1,\dots,x_n)$ is a multi-affine function, is, in some cases, equal to $(n-1)$. 
@article{ZVMMF_2015_55_4_a17,
     author = {S. N. Selezneva},
     title = {On the multiplicative complexity of some {Boolean} functions},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {730--736},
     year = {2015},
     volume = {55},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_4_a17/}
}
TY  - JOUR
AU  - S. N. Selezneva
TI  - On the multiplicative complexity of some Boolean functions
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2015
SP  - 730
EP  - 736
VL  - 55
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_4_a17/
LA  - ru
ID  - ZVMMF_2015_55_4_a17
ER  - 
%0 Journal Article
%A S. N. Selezneva
%T On the multiplicative complexity of some Boolean functions
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2015
%P 730-736
%V 55
%N 4
%U http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_4_a17/
%G ru
%F ZVMMF_2015_55_4_a17
S. N. Selezneva. On the multiplicative complexity of some Boolean functions. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 4, pp. 730-736. http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_4_a17/

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

[2] Vouar J., Peralta R., Pochuev D., “On the multiplicative complexity of Boolean functions over the basis $\{\land,\oplus,1\}$”, Theoretical Comput. Sci., 235 (2000), 43–57 | MR

[3] Schnorr C. P., “The multiplicative complexity of boolean functions”, Proc. 6th Internat. Conf. AAECC-6, Lecture Notes in Computer Science, 357, Springer, Berlin, 1989, 45–58 | MR

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

[5] Boyar J., Peralta R., Pochuev D., Concrete multiplicative complexity of symmetric functions, Technical Report YALEU/DCS/TR1219, Computer Science Department, Yale University, 2001

[6] Boyar J., Peralta R., The exact multiplicative complexity of the hamming weight function

[7] Krasnova T. I., “O kon'yunktivnoi slozhnosti skhem v bazise Zhegalkina dlya odnoi posledovatelnosti bulevykh funktsii”, Diskretnaya matem. i ee prilozheniya, Materialy XI Mezhdunar. seminara, Izd-vo mekhan.-matem. f-ta MGU, M., 2012, 138–141

[8] Kojevnikov A., Kulikov A. S., “Circuit complexity and multiplicative complexity of boolean functions”, Proc. of 6th Conf. on Computability (CiE 2010), Lecture Notes in Computer Science, 6158, Springer, Berlin, 2010, 239–245 | MR | Zbl

[9] Sergeev I. S., A relation between additive and multiplicative complexity of boolean functions, 2013, arXiv: 1303.4177

[10] Schaefer T. J., “The complexity of satisfiability problems”, Proc. of the 10th ACM Symposium on Theory of Computing (1978), 216–226 | MR | Zbl

[11] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Vyssh. shkola, M., 2001

[12] Kurosh A. G., Kurs vysshei algebry, Nauka, M., 1971