Geodesic
On the number of significant variables of balanced Boolean function with the fixed number of elementary conjunctions in its DNF
Matematičeskie voprosy kriptografii, Tome 2 (2011) no. 4, pp. 37-47 
V. G. Nikonov. On the number of significant variables of balanced Boolean function with the fixed number of elementary conjunctions in its DNF. Matematičeskie voprosy kriptografii, Tome 2 (2011) no. 4, pp. 37-47. http://geodesic.mathdoc.fr/item/MVK_2011_2_4_a2/
@article{MVK_2011_2_4_a2,
     author = {V. G. Nikonov},
     title = {On the number of significant variables of balanced {Boolean} function with the fixed number of elementary conjunctions in its {DNF}},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {37--47},
     year = {2011},
     volume = {2},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2011_2_4_a2/}
}
TY  - JOUR
AU  - V. G. Nikonov
TI  - On the number of significant variables of balanced Boolean function with the fixed number of elementary conjunctions in its DNF
JO  - Matematičeskie voprosy kriptografii
PY  - 2011
SP  - 37
EP  - 47
VL  - 2
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/MVK_2011_2_4_a2/
LA  - ru
ID  - MVK_2011_2_4_a2
ER  - 
%0 Journal Article
%A V. G. Nikonov
%T On the number of significant variables of balanced Boolean function with the fixed number of elementary conjunctions in its DNF
%J Matematičeskie voprosy kriptografii
%D 2011
%P 37-47
%V 2
%N 4
%U http://geodesic.mathdoc.fr/item/MVK_2011_2_4_a2/
%G ru
%F MVK_2011_2_4_a2

Voir la notice de l'article provenant de la source Math-Net.Ru

The upper and lower bounds for the number $n(k)$ of significant variables of balanced Boolean function represented by $k$ elementary conjunction are obtained. The boundedness of $n(k)$ for every $k$ was proved by the author previously. Balanced Boolean functions are very important for cryptography; their DNF representations correspond to realizations by circuits, in particular, by programmable logical matrices.

[1] Nikonov V. G., “Konechnost nekotorykh klassov bulevykh funktsii s ogranichennym chislom elementarnykh kon'yunktsii v DNF”, Vestnik RUDN, 2:1 (2003), 68–78

[2] Nikonov V. G., “O suschestvovanii minimalnoi, no ne kratchaishei ortogonalnoi diz'yunktivnoi normalnoi formy”, Trudy po diskretnoi matematike, 10, Fizmatlit, M., 2007, 188–201

[3] Zhuravlev Yu. I., “Ob algoritmakh uproscheniya diz'yunktivnykh normalnykh form”, Dokl. AN SSSR, 132:2 (1960), 260–263 | Zbl

[4] Zakrevskii A. D., Logicheskii sintez kaskadnykh skhem, Nauka, M., 1981 | MR

[5] Mc.Gluskey E. J., “Minimization of Boolean Functions”, Bell Syst. Techn. J., 35:6 (1956), 1417–1444 | MR

[6] Nikonov V. G., “Porogovye predstavleniya bulevykh funktsii”, Obozr. prikl. i promyshl. matem., 1:3 (1994), 402–457 | Zbl

[7] Nikonov V. G., “Klassifikatsiya minimalnykh bazisnykh predstavlenii vsekh bulevykh funktsii ot chetyrekh peremennykh”, Obozr. prikl. i promyshl. matem., 1:3 (1994), 458–545 | Zbl

[8] Nikonov V. G., “Pokrytiya bulevykh grafov”, Diskret. matem., 6:4 (1994), 21–34 | MR | Zbl