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, 2017, Volume 22, Pages 18–30
DOI: https://doi.org/10.26516/1997-7670.2017.22.18
(Mi iigum320)
 

Lower bound of the complexity of seven-valued functions in the class of polarized polynomials

A. S. Baliuk, A. S. Zinchenko

Irkutsk State University, 1, K. Marx st., Irkutsk, 664003, Russian Federation
References:
Abstract: One of the directions of the investigation of functions over finite fields is the study of their representations, including polynomial ones. In the area of polynomial representations of functions the problem of estimating the complexity of such representations can be highlighted.
The complexity of the polynomial, representing the function, is the number of its non-zero terms. Each function can be represented by several different polynomials from the same class. The complexity of a function in the class of polynomials is the least possible complexity of a polynomial from this class, representing the function. The complexity of the given set of functions in the class of polynomials is the maximal complexity of a function from the set in this class of polynomials.
In the case of functions over a finite field of order 2 (Boolean functions), exact values of the complexity of such representations are known for many classes of polynomial forms. But for functions over finite fields of order greater than two, even in fairly simple classes of polynomials, only mismatched upper and lower bounds of complexity have been found.
This paper is devoted to the study of the representation of seven-valued functions by polarized polynomials. The polynomials of this class have the form of a sum of a finite number of products of a certain type.
For the case of Boolean and three-valued functions, effective lower bounds for the complexity in the class of polarized polynomials are known, as well as a weaker power estimate for functions over a finite field of prime order.
In previous papers, the authors obtained effective lower bounds for the complexity of functions over finite fields of order 4 and 5 in the class of polarized polynomials.
In this paper an effective lower bound for the complexity of seven-valued functions in the class of polarized polynomials has been obtained.
Keywords: finite field, polarized polynomial, Kroneker form, complexity, lower bounds.
Bibliographic databases:
Document Type: Article
UDC: 519.714.4
MSC: 68Q17
Language: Russian
Citation: A. S. Baliuk, A. S. Zinchenko, “Lower bound of the complexity of seven-valued functions in the class of polarized polynomials”, Bulletin of Irkutsk State University. Series Mathematics, 22 (2017), 18–30
Citation in format AMSBIB
\Bibitem{BalZin17}
\by A.~S.~Baliuk, A.~S.~Zinchenko
\paper Lower bound of the complexity of seven-valued functions in the class of polarized polynomials
\jour Bulletin of Irkutsk State University. Series Mathematics
\yr 2017
\vol 22
\pages 18--30
\mathnet{http://mi.mathnet.ru/iigum320}
\crossref{https://doi.org/10.26516/1997-7670.2017.22.18}
Linking options:
  • https://www.mathnet.ru/eng/iigum320
  • https://www.mathnet.ru/eng/iigum/v22/p18
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Statistics & downloads:
    Abstract page:160
    Full-text PDF :56
    References:22
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024