Recently, the interest to polynomial representations of functions over finite fields and over finite rings is being increased. Complexity of those representations is widely studied.

This paper introduces new upper bounds on complexity of discrete functions over particular finite fields in class of polarized polynomials. The results are state in the terms of matrix forms. A matrix form is representation of functions vector of values as a product of nonsingular matrix and a vector of coefficients. The complexity of matrix form of a special kind is equal to complexity of polarized polynomial for same function. A complexity of a matrix form is a number of nonzero coefficients in its vector. Every function can be represented by variety of matrix forms of the same class.

A complexity of a function in a class of matrix forms is the minimal complexity of forms in the class representing this function.

This paper introduces new upper bounds on complexity of functions in class of polarized polynomials over fields of orders 2^k and p^k, p is prime and p ⩾ 3.

MSC

68Q17

1. Baliuk A. S., Yanushkovsky G.V. Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms (in Russian). Izvestiya Irkustkogo gosudarstvennogo universiteta. Series Mathematics, 2015, vol. 14, pp. 3-17.

2. Baliuk A.S., Zinchenko A.S. Lower bound on complexity of functions over finite field of order 4 in class of polarized polynomials (in Russian). Izvestiya Irkustkogo gosudarstvennogo universiteta. Series Mathematics, 2016, vol. 16, pp. 19-29.

3. Graham R., Knuth D., Patashnik O. Concrete Mathmatics. A Foundation for Computer Science. Addison Wesley, 1994. 672 p.

4. Zinchenko A.S., Panteleev V.I. Polinomial operator representations of k-valued functions (in Russian). Diskretnyi Analiz i Issledovanie Operatsii. Series 1, 2006, vol. 13, no 3, pp. 13–26.

5. Lidl R., Niederreiter H. Finite Fields (Encyclopedia of Mathematics and its Applications). Cambridge University Press, England, 1984. 660 p.

6. 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, 2012, vol. 36, issue 3, pp. 150–154.

7. Peryazev N.A. The complexity of Boolean functions in the class of polarized polynomial forms (in Russian). Algebra and Logic, 1995, vol. 34, no 3, pp. 323–326.

8. Selezneva S.N. On the complexity of representation of k-valued functions by generalised polarised polynomials. Discrete Mathematics and Applications, 2010, vol. 19, issue 6, pp. 653–663.

9. Selezneva S.N. On the complexity of representations of functions over multivalued logics by polarized polynomials (in Russian). Discrete Mathematics and Applications, 2002, vol. 14, no 2. pp. 48–53.