On the multiplicative complexity of quasi-quadratic boolean functions
The multiplicative complexity $\mu(f)$ of a boolean function $f(x_1,\ldots,x_n)$ is the number of $\&$-gates in circuits that are in the basis $\{\&,\oplus,1\}$ and that compute the function $f$. A boolean function $f(x_1,\ldots,x_n)$ is a quasi-quadratic if $f$ can be represented in the form $\varphi(x_1,\ldots,x_k)\oplus q(x_1,\ldots,x_n)$ where $\varphi$ is an arbitrary function, and $q$ is a quadratic function (i.e. a function of the degree $2$), $k\le n$. In this paper, we study the multiplicative complexity of quasi-quadratic boolean functions if $k=3$, $n$ is an arbitrary number. We prove that if $f(x_1,\ldots,x_n)$ if a quasi-quadratic boolean function where $k=3$, and $n\ge k$, then $\mu(f)\le \lceil (n+1)/2\rceil$ where $\lceil a\rceil$ denotes the smallest integer number that is no smaller then $a$. Besides, we describe a sequence of quasi-quadratic Boolean functions $f_n(x_1,\ldots,x_n)$, $k=3$, $n=5,6,\ldots$, and we prove for this sequence that $\mu(f_n)\ge \lceil(n+1)/2\rceil$.