NDLI: On the multiplicative complexity of quasi-quadratic Boolean functions

Please wait, while we are loading the content...

Moscow University Computational Mathematics and Cybernetics : Volume 41

Moscow University Computational Mathematics and Cybernetics : Volume 40

Moscow University Computational Mathematics and Cybernetics : Volume 39

Moscow University Computational Mathematics and Cybernetics : Volume 39, Issue 4, October 2015

Moscow University Computational Mathematics and Cybernetics : Volume 39, Issue 3, July 2015

Moscow University Computational Mathematics and Cybernetics : Volume 39, Issue 2, April 2015

Moscow University Computational Mathematics and Cybernetics : Volume 39, Issue 1, January 2015

Inverse problem of determining the thickness of optical coatings layers from the data of monochromatic control

Limit distribution of a risk estimate using the vaguelette-wavelet decomposition of signals in a model with correlated noise

Complexity of the search for the least solution to a system of dictionary equations of exponential type

On the multiplicative complexity of quasi-quadratic Boolean functions

Synthesis of circuits admitting complete checking tests of constant length under inverse faults at outputs of elements

On tests detecting certain faults of circuit inputs for almost all Boolean functions

Comparison of families of algorithms for recognizing abnormal behavior of dynamic systems

Moscow University Computational Mathematics and Cybernetics : Volume 38

Moscow University Computational Mathematics and Cybernetics : Volume 37

Moscow University Computational Mathematics and Cybernetics : Volume 36

Moscow University Computational Mathematics and Cybernetics : Volume 35

Moscow University Computational Mathematics and Cybernetics : Volume 34

Moscow University Computational Mathematics and Cybernetics : Volume 33

Moscow University Computational Mathematics and Cybernetics : Volume 32

Moscow University Computational Mathematics and Cybernetics : Volume 31

On the multiplicative complexity of quasi-quadratic Boolean functions

Content Provider	Springer Nature Link
Author	Selezneva, S. N.
Copyright Year	2015
Abstract	The multiplicative complexity μ(f) of Boolean function f(x $_{1}$, …, x $_{ n }$) is the smallest number of AND gates in the circuits of basis {&, ⊕, 1} such that each circuit executes function f. Boolean function f(x $_{1}$, …, x $_{ n }$) is quasi-quadratic if it can be presented as φ(x $_{1}$, …, x $_{ k }$) ⊕ q(x $_{1}$, …, x $_{ n }$), where φ is an arbitrary function, q is a quadratic function (i.e., a function of degree), k ≤ n. This work is concerned with the multiplicative complexity of quasi-quadratic functions with k = 3 and arbitrary n. We prove that if f(x $_{1}$, …, x $_{ n }$) is a quasi-quadratic Boolean function where k = 3, n ≥ k, then μ(f) ≤ ⌈(n + 1)/2⌉, where ⌈a⌉ denotes the smallest integer not less than a. In addition, we describe the family of quasi-quadratic Boolean functions f $_{ n }$(x $_{1}$, …, x $_{ n }$), k = 3, n = 5, 6, …, for which we prove that μ(f $_{ n }$) = ⌈(n + 1)/2⌉.
Starting Page	18
Ending Page	25
Page Count	8
File Format	PDF
ISSN	02786419
Journal	Moscow University Computational Mathematics and Cybernetics
Volume Number	39
Issue Number	1
e-ISSN	19348428
Language	English
Publisher	Allerton Press
Publisher Date	2015-02-27
Publisher Place	Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Boolean function quadratic function quasi-quadratic function Zhegalkin polynomial multiplicative complexity upper bound lower bound Mathematics
Content Type	Text
Resource Type	Article
Subject	Control and Optimization Human-Computer Interaction Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

On the multiplicative complexity of some Boolean functions

Upper bounds on the depth of symmetric Boolean functions

Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables

A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials

On quasi-universal word functions

On a method of derivation of lower bounds for the nonlinearity of Boolean functions

On the generation of false images of linear Boolean functions

On the multiplicative complexity of quasi-quadratic Boolean functions

Similar Documents

On the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

On the multiplicative complexity of some Boolean functions

Upper bounds on the depth of symmetric Boolean functions

Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables

A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials

On quasi-universal word functions

On a method of derivation of lower bounds for the nonlinearity of Boolean functions

On the generation of false images of linear Boolean functions

On the multiplicative complexity of quasi-quadratic Boolean functions