Diskretnaya Matematika
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



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretnaya Matematika, 2014, Volume 26, Issue 4, Pages 100–109
DOI: https://doi.org/10.4213/dm1308
(Mi dm1308)
 

This article is cited in 2 scientific papers (total in 2 papers)

Multiplicative complexity of some Boolean functions

S. N. Selezneva

M. V. Lomonosov Moscow State University
References:
Abstract: The multiplicative (or conjunctive) complexity of a Boolean function $f(x_1, \dots, x_n)$ (respectively, of a system of Boolean functions $F = \{f_1, \dots, f_m\}$) is the smallest number of AND gates in circuits in the basis $\{x\& y, x \oplus y, 1\}$ implementing the function $f$ (respectively, all the functions of system $F$). The multiplicative complexity of a function $f$ (of a system of functions $F$) will be denoted by $\mu(f)$ (respectively, $\mu(F)$). It will be shown that $\mu(f) = n-1$ if a function $f(x_1, \dots, x_n)$ is representable as $x_1x_2\dots x_n \oplus q(x_1, \dots, x_n)$, where $q$ is a function of degree two ($n \ge 3$). Moreover, we show that $\mu(f) \le n-1$ if a function $f(x_1, \dots, x_n)$ is representable as a XOR sum of two multiaffine functions. Furthermore, $\mu(F) = n-1$ if $F = \{x_1x_2\dots x_n, f(x_1, \dots, x_n)\}$, where $f$ is a function of degree two or a multiaffine function.
Keywords: Boolean function, circuit, complexity, multiplicative (conjunctive) complexity, the upper bound.
Funding agency Grant number
Russian Foundation for Basic Research 13-01-00684-а
13-01-00958-а
Received: 23.05.2014
English version:
Discrete Mathematics and Applications, 2015, Volume 25, Issue 2, Pages 101–108
DOI: https://doi.org/10.1515/dma-2015-0010
Bibliographic databases:
Document Type: Article
UDC: 519.713
Language: Russian
Citation: S. N. Selezneva, “Multiplicative complexity of some Boolean functions”, Diskr. Mat., 26:4 (2014), 100–109; Discrete Math. Appl., 25:2 (2015), 101–108
Citation in format AMSBIB
\Bibitem{Sel14}
\by S.~N.~Selezneva
\paper Multiplicative complexity of some Boolean functions
\jour Diskr. Mat.
\yr 2014
\vol 26
\issue 4
\pages 100--109
\mathnet{http://mi.mathnet.ru/dm1308}
\crossref{https://doi.org/10.4213/dm1308}
\mathscinet{https://mathscinet.ams.org/mathscinet-getitem?mr=3467229}
\elib{https://elibrary.ru/item.asp?id=22834165}
\transl
\jour Discrete Math. Appl.
\yr 2015
\vol 25
\issue 2
\pages 101--108
\crossref{https://doi.org/10.1515/dma-2015-0010}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000366853400004}
\elib{https://elibrary.ru/item.asp?id=24023422}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84927937365}
Linking options:
  • https://www.mathnet.ru/eng/dm1308
  • https://doi.org/10.4213/dm1308
  • https://www.mathnet.ru/eng/dm/v26/i4/p100
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретная математика
    Statistics & downloads:
    Abstract page:561
    Full-text PDF :239
    References:74
    First page:36
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025