Bulletin of Irkutsk State University. Series Mathematics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Bulletin of Irkutsk State University. Series Mathematics:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Bulletin of Irkutsk State University. Series Mathematics, 2015, Volume 14, Pages 3–17 (Mi iigum239)  

This article is cited in 6 scientific papers (total in 6 papers)

Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms

A. S. Baliuka, G. V. Yanushkovskyb

a Irkutsk State University, 1, K. Marx st., Irkutsk, 664003
b Higher School of Economics, 20, Myasnitskaya st., Moscow, 101000
Full-text PDF (294 kB) Citations (6)
References:
Abstract: 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, polynomial, Kroneker form, complexity.
Funding agency Grant number
Russian Foundation for Basic Research 13-01-00621
Document Type: Article
UDC: 519.715
Language: Russian
Citation: A. S. Baliuk, G. V. Yanushkovsky, “Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms”, Bulletin of Irkutsk State University. Series Mathematics, 14 (2015), 3–17
Citation in format AMSBIB
\Bibitem{BalYan15}
\by A.~S.~Baliuk, G.~V.~Yanushkovsky
\paper Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms
\jour Bulletin of Irkutsk State University. Series Mathematics
\yr 2015
\vol 14
\pages 3--17
\mathnet{http://mi.mathnet.ru/iigum239}
Linking options:
  • https://www.mathnet.ru/eng/iigum239
  • https://www.mathnet.ru/eng/iigum/v14/p3
  • This publication is cited in the following 6 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Statistics & downloads:
    Abstract page:225
    Full-text PDF :60
    References:51
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024