BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2019 >
Volume 13, Number 1-2 >

Please use this identifier to cite or link to this item:

Title: Distribution of The Boolean Functions of n Variables According to Their Algebraic Degrees
Authors: Bakoev, Valentin
Keywords: Boolean Function
Algebraic Degree
Issue Date: 2019
Publisher: Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation: Serdica Journal of Computing, Vol. 13, No 1-2, (2019), 017p-026p
Abstract: Knowledge on the enumeration and distribution of Boolean functions according to their algebraic degrees is important for the theory as well as for its applications. As of now, this knowledge is not complete; for example, it is well-known that half of all Boolean functions have a maximal algebraic degree. In this paper, a formula for the number of all Boolean functions of n variables and algebraic degree = k is derived. A direct consequence from it is the assertion (formulated already by Claude Carlet) that when n →∞, almost half of all Boolean functions of n variables have an algebraic degree = n−1. The results obtained by this formula were used in creating the sequence A319511 in the OEIS. The discrete probability of a random Boolean function having a certain algebraic degree is defined and the corresponding distribution is computed, for 3 ≤ n ≤ 10. Four applications are considered: at the design and analysis of efficient algorithms for exact or probabilistic computing the algebraic degree of Boolean functions; when checking 4 test files for representativeness; when creating benchmark files of Boolean functions.
ISSN: 1312-6555
Appears in Collections:Volume 13, Number 1-2

Files in This Item:

File Description SizeFormat
sjc-vol13-num1-2-2019-p017-p026.pdf304.12 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License