Upper bound for the length of functions over a finite field in the class of pseudopolynomials


Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Somente assinantes

Resumo

An exclusive-OR sum of pseudoproducts (ESPP), or a pseudopolynomial over a finite field is a sum of products of linear functions. The length of an ESPP is defined as the number of its pairwise distinct summands. The length of a function f over this field in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function LkESPP(n) on the set of functions over a finite field of k elements in the class of ESPPs is considered; it is defined as the maximum length of a function of n variables over this field in the class of ESPPs. It is proved that LkESPP(n) = O(kn/n2).

Sobre autores

S. Selezneva

Faculty of Computational Mathematics and Cybernetics

Autor responsável pela correspondência
Email: selezn@cs.msu.su
Rússia, Moscow, 119991

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML

Declaração de direitos autorais © Pleiades Publishing, Ltd., 2017