Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
Find






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


Zh. Vychisl. Mat. Mat. Fiz., 2017, Volume 57, Number 5, Pages 899–904 (Mi zvmmf10580)  

This article is cited in 1 scientific paper (total in 1 paper)

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

S. N. Selezneva

Faculty of Computational Mathematics and Cybernetics, Moscow State University, Moscow, Russia

Abstract: 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 $L_k^{ESPP}(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 $L_k^{ESPP}(n)=O(k^n/n^2)$.

Key words: function over a finite field, polynomial form, exclusive-OR sum of pseudoproducts, length, upper bound.

Funding Agency Grant Number
Russian Foundation for Basic Research 13-01-00684_а


DOI: https://doi.org/10.7868/S0044466917050118

Full text: PDF file (115 kB)
References: PDF file   HTML file

English version:
Computational Mathematics and Mathematical Physics, 2017, 57:5, 898–903

Bibliographic databases:

UDC: 519.7
Received: 13.04.2016

Citation: S. N. Selezneva, “Upper bound for the length of functions over a finite field in the class of pseudopolynomials”, Zh. Vychisl. Mat. Mat. Fiz., 57:5 (2017), 899–904; Comput. Math. Math. Phys., 57:5 (2017), 898–903

Citation in format AMSBIB
\Bibitem{Sel17}
\by S.~N.~Selezneva
\paper Upper bound for the length of functions over a finite field in the class of pseudopolynomials
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2017
\vol 57
\issue 5
\pages 899--904
\mathnet{http://mi.mathnet.ru/zvmmf10580}
\crossref{https://doi.org/10.7868/S0044466917050118}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3661126}
\elib{https://elibrary.ru/item.asp?id=29331743}
\transl
\jour Comput. Math. Math. Phys.
\yr 2017
\vol 57
\issue 5
\pages 898--903
\crossref{https://doi.org/10.1134/S0965542517050116}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000403459000013}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85020631163}


Linking options:
  • http://mi.mathnet.ru/eng/zvmmf10580
  • http://mi.mathnet.ru/eng/zvmmf/v57/i5/p899

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. S. Baliuk, “Complexity lower bound for Boolean functions in the class of extended operator forms”, Izvestiya Irkutskogo gosudarstvennogo universiteta. Seriya Matematika, 30 (2019), 125–140  mathnet  crossref
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Number of views:
    This page:128
    Full text:11
    References:30
    First page:17

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022