Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Zh. Vychisl. Mat. Mat. Fiz.: Year: Volume: Issue: Page: Find

 Zh. Vychisl. Mat. Mat. Fiz., 2015, Volume 55, Number 4, Pages 730–736 (Mi zvmmf10197)

On the multiplicative complexity of some Boolean functions

S. N. Selezneva

Moscow State University, Moscow, 119992, Russia

Abstract: 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…x_n\oplus q(x_1,…,x_n)$, where the degree of the function $q(x_1,…,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…x_n\oplus r(x_1,…,x_n)$, where $r(x_1,…,x_n)$ is a multi-affine function, is, in some cases, equal to $(n-1)$.

Key words: Boolean function, circuit, complexity, multiplicative complexity, upper bound.

DOI: https://doi.org/10.7868/S0044466915040122

Full text: PDF file (205 kB)
References: PDF file   HTML file

English version:
Computational Mathematics and Mathematical Physics, 2015, 55:4, 724–730

Bibliographic databases:

UDC: 519.7
MSC: Primary 68Q19; Secondary 06E30, 94D05

Citation: S. N. Selezneva, “On the multiplicative complexity of some Boolean functions”, Zh. Vychisl. Mat. Mat. Fiz., 55:4 (2015), 730–736; Comput. Math. Math. Phys., 55:4 (2015), 724–730

Citation in format AMSBIB
\Bibitem{Sel15} \by S.~N.~Selezneva \paper On the multiplicative complexity of some Boolean functions \jour Zh. Vychisl. Mat. Mat. Fiz. \yr 2015 \vol 55 \issue 4 \pages 730--736 \mathnet{http://mi.mathnet.ru/zvmmf10197} \crossref{https://doi.org/10.7868/S0044466915040122} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3343132} \zmath{https://zbmath.org/?q=an:06458245} \elib{https://elibrary.ru/item.asp?id=23299898} \transl \jour Comput. Math. Math. Phys. \yr 2015 \vol 55 \issue 4 \pages 724--730 \crossref{https://doi.org/10.1134/S0965542515040119} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000354067600017} \elib{https://elibrary.ru/item.asp?id=24028030} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84928905755} 

• http://mi.mathnet.ru/eng/zvmmf10197
• http://mi.mathnet.ru/eng/zvmmf/v55/i4/p730

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Selezneva S.N., “On the Multiplicative Complexity of Boolean Functions”, Fundam. Inform., 145:3 (2016), 399–404
•  Number of views: This page: 108 Full text: 18 References: 29 First page: 7