On the multiplicative complexity of some Boolean functions

S. N. Selezneva

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 4, pp. 730-736

Résumé

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)$.