Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Известия Иркутского ...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
addClaim

Upper Bounds of the Complexity of Functions over Finite Fields in Some Classes of Kroneker Forms

Authors: A.S. Baliuk; G.V. Yanushkovsky;

Upper Bounds of the Complexity of Functions over Finite Fields in Some Classes of Kroneker Forms

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

Kroneker form, polynomial, QA1-939, complexity, finite field, Mathematics

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
gold