Geodesic
Distribution of The Boolean Functions of n Variables According to Their Algebraic Degrees
Serdica Journal of Computing, Tome 13 (2019) no. 1-2, pp. 017-026

Voir la notice de l'article provenant de la source Bulgarian Digital Mathematics Library

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.
Keywords: Boolean Function, Cryptography, Algebraic Degree, Enumeration, Distribution 
@article{SJC_2019_13_1-2_a1,
     author = {Bakoev, Valentin},
     title = {Distribution of {The} {Boolean} {Functions} of n {Variables} {According} to {Their} {Algebraic} {Degrees}},
     journal = {Serdica Journal of Computing},
     pages = {017--026},
     publisher = {mathdoc},
     volume = {13},
     number = {1-2},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJC_2019_13_1-2_a1/}
}
TY  - JOUR
AU  - Bakoev, Valentin
TI  - Distribution of The Boolean Functions of n Variables According to Their Algebraic Degrees
JO  - Serdica Journal of Computing
PY  - 2019
SP  - 017
EP  - 026
VL  - 13
IS  - 1-2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJC_2019_13_1-2_a1/
LA  - en
ID  - SJC_2019_13_1-2_a1
ER  - 
%0 Journal Article
%A Bakoev, Valentin
%T Distribution of The Boolean Functions of n Variables According to Their Algebraic Degrees
%J Serdica Journal of Computing
%D 2019
%P 017-026
%V 13
%N 1-2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJC_2019_13_1-2_a1/
%G en
%F SJC_2019_13_1-2_a1
Bakoev, Valentin. Distribution of The Boolean Functions of n Variables According to Their Algebraic Degrees. Serdica Journal of Computing, Tome 13 (2019) no. 1-2, pp. 017-026. http://geodesic.mathdoc.fr/item/SJC_2019_13_1-2_a1/