Geodesic
Complexity lower bound for Boolean functions in the class of extended operator forms
The Bulletin of Irkutsk State University. Series Mathematics, Tome 30 (2019), pp. 125-140

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

Starting with the fundamental work of D.E.Muller in 1954, the polynomial representations of Boolean functions are widely investigated in connection with the theory of coding and for the synthesis of circuits of digital devices. The operator approach to polynomial representations, proposed in the works of S. F. Vinokurov, made it possible, on the one hand, to uniformly describe all known types of polynomial forms of Boolean functions, and, on the other hand, to generalize them to the case of expansions by the operator images of arbitrary odd function, not only conjunction. In the study of polynomial and, in the general case, operator forms, one of the main questions is obtaining lower and upper bounds of the complexity of the representation of Boolean functions in various classes of forms. The upper bounds of complexity are actually algorithms for minimizing Boolean functions in a particular class of forms. The lower bounds of complexity can be divided into two types: combinatorial and effective. Combinatorial lower bounds make it possible to prove the existence of Boolean functions, having high complexity, without finding the explicit form of these functions. Effective lower bounds are based on explicit constructing Boolean functions that have high complexity in a particular class of forms. In this paper, using an algebraic extension of a finite field of order 2, we obtain a lower bound for the complexity of Boolean functions in the class of extended operator forms. This lower bound strengthens the previously known lower bounds for this class of operator forms and is becoming asymptotically optimal if the sequence of Mersenne primes is infinite.
Keywords: Boolean function, lower bound, extension of finite field
Mots-clés : Mersenne prime. 
A. S. Baliuk. Complexity lower bound for Boolean functions in the class of extended operator forms. The Bulletin of Irkutsk State University. Series Mathematics, Tome 30 (2019), pp. 125-140. http://geodesic.mathdoc.fr/item/IIGUM_2019_30_a9/
@article{IIGUM_2019_30_a9,
     author = {A. S. Baliuk},
     title = {Complexity lower bound for {Boolean} functions in the class of extended operator forms},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {125--140},
     year = {2019},
     volume = {30},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2019_30_a9/}
}
TY  - JOUR
AU  - A. S. Baliuk
TI  - Complexity lower bound for Boolean functions in the class of extended operator forms
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2019
SP  - 125
EP  - 140
VL  - 30
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2019_30_a9/
LA  - en
ID  - IIGUM_2019_30_a9
ER  - 
%0 Journal Article
%A A. S. Baliuk
%T Complexity lower bound for Boolean functions in the class of extended operator forms
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2019
%P 125-140
%V 30
%U http://geodesic.mathdoc.fr/item/IIGUM_2019_30_a9/
%G en
%F IIGUM_2019_30_a9

[1] A000043 OEIS, The On-Line Encyclopedia of Integer Sequences, , URL (data obrascheniya: 24.08.2019) https://oeis.org/A000043

[2] A. S. Baliuk, A. S. Zinchenko, “Lower Bounds of Complexity for Polarized Polynomials over Finite Fields”, Siberian Mathematical Journal, 60:1 (2019), 1–9 | DOI | DOI | MR | Zbl

[3] A. S. Baliuk, G. V. Yanushkovskiy, “Operator polynomial forms of functions over finite fields”, Proceedings of IX International conference “Diskretnye modeli v teorii upravlyayushchikh sistem”, MAKS Press, M., 2015, 28–30 (in Russian)

[4] B. C. Berndt, R. J. Evans, K. S. Williams, Gauss and Jacobi sums, John Wiley Sons Inc., Toronto, 1998, 600 pp. | MR | Zbl

[5] A. S. Frantseva, “Complexity of Boolean functions' representations in classes of extended pair-generated operator forms”, Siberian Electronic Mathematical Reports, 16 (2019), 523–541 (in Russian) | DOI | MR | Zbl

[6] Vinokurov S. F., N. A. Peryazev (red.), Selected questions in the theory of Boolean functions, Fizmatlit, M., 2001, 192 pp. (in Russian)

[7] R. Lidl, H. Niederreiter, Finite Fields (Encyclopedia of Mathematics and its Applications, Cambridge University Press, England, 1984, 660 pp. | DOI | MR | MR | Zbl

[8] N. K. Markelov, “A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials”, Moscow Univ. Comput. Math. Cybern., 36:3 (2012), 150–154 | DOI | MR | Zbl

[9] D. E. Muller, “Application of Boolean algebra to switching circuit design and to error detection”, IRE Trans. Electron. Comput., EC-3:3 (1954), 6–12 | DOI | MR

[10] N. A. Peryazev, “Complexity of Boolean functions in the class of polarized polynomial forms”, Algebra and Logic, 34:3 (1995), 177–179 | DOI | MR | Zbl

[11] S. N. Selezneva, “Upper Bound for the Length of Functions over a Finite Field in the Class of Pseudopolynomials”, Computational Mathematics and Mathematical Physics, 57:5 (2017), 898–903 | DOI | DOI | MR | Zbl

[12] S. F. Vinokurov, Mixed operators in Boolean functions and their properties, Series Discrete mathematics and informatics, 12, Irkutsk University, Irkutsk, 2000, 36 pp. (in Russian)