Geodesic
Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms
The Bulletin of Irkutsk State University. Series Mathematics, Tome 14 (2015), pp. 3-17 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Polynomial representations of Boolean functions have been studied well enough. Recently, the interest to polynomial representations of functions over finite fields and over finite rings is being increased. There are a lot of difficulties in studying of the complexity of these representations. Only not equal upper and lower bounds has been obtained, even for sagnificantly simple classes of polynomials. This paper is about polarized polynomials over finite fields and their generalizations: differentially and generically polarized polynomials. Such a polynomial is a finite sum of products. The difference between classes of polynomials is in constraints, applied to the products. Every polynomial represents an $n$-variable function over finite field. A complexity of a polynomial is a number of nonzero summands in it. Every function can be represented by several polynomials, which are belongs to the same class. A complexity of a function in a class of polynomials is the minimal complexity of polynomials in the class, which represent this function. Previously, the upper bounds were known for arbitrary $n$-variable function over primary finite field of order, greater than 2, for the classes of polarized and differentially polarized polynomials, as well as for the class of generically polarized polynomials. A representation of an $n$-ary function over finite field of order $q$ by a polarized polynomial or its generalization can be considered as a Kroneker form. This means, that the function, considered as a vector in appropriate linear space, is computed by a linear transformation of a vector of coefficients of the polynomial, where the matrix of this linear transformation is a Kroneker product of $n$ nonsingular matrices with rank $q$. This approach helped us to improve the upper bound for polarized and differentially polarized polynomials for the case of any finite field of odd order, and to improve the upper bound for generically polarized polynomials for the case of any finite field of order, greater than 2.
Keywords: finite field, Kroneker form, complexity.
Mots-clés : polynomial 
@article{IIGUM_2015_14_a0,
     author = {A. S. Baliuk and G. V. Yanushkovsky},
     title = {Upper bounds of the complexity of functions over finite fields in some classes of {Kroneker} forms},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {3--17},
     year = {2015},
     volume = {14},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2015_14_a0/}
}
TY  - JOUR
AU  - A. S. Baliuk
AU  - G. V. Yanushkovsky
TI  - Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2015
SP  - 3
EP  - 17
VL  - 14
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2015_14_a0/
LA  - ru
ID  - IIGUM_2015_14_a0
ER  - 
%0 Journal Article
%A A. S. Baliuk
%A G. V. Yanushkovsky
%T Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2015
%P 3-17
%V 14
%U http://geodesic.mathdoc.fr/item/IIGUM_2015_14_a0/
%G ru
%F IIGUM_2015_14_a0
A. S. Baliuk; G. V. Yanushkovsky. Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms. The Bulletin of Irkutsk State University. Series Mathematics, Tome 14 (2015), pp. 3-17. http://geodesic.mathdoc.fr/item/IIGUM_2015_14_a0/

[1] Graham R., Knuth D., Patashnik O., Concrete Mathmatics. A Foundation for Computer Science, Addison Wesley, 1994, 672 pp. | MR

[2] Zinchenko A. S., Panteleev V. I., “Polinomialnie operatornie predstavlenija funkcij $k$-znachnoj logiki”, Diskretnyi Analiz i Issledovanie Operatsii. Series 1, 13:3 (2006), 13–26 (in Russian) | MR

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

[4] Markelov N. K., “A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials”, Moscow University Computational Mathematics and Cybernetics, 36:3 (2012), 150–154 | DOI | MR | MR | Zbl

[5] Peryazev N. A., “The complexity of Boolean functions in the class of polarized polynomial forms”, Algebra and Logic, 34:3 (1995), 323–326 (in Russian) | MR | Zbl

[6] Selezneva S. N., “On the complexity of representation of $k$-valued functions by generalised polarised polynomials”, Discrete Mathematics and Applications, 19:6 (2010), 653–663 | DOI | MR | Zbl

[7] Selezneva S. N., “On the complexity of representations of functions over multivalued logics by polarized polynomials”, Discrete Mathematics and Applications, 14:2 (2002), 48–53 (in Russian) | DOI | Zbl