Lower bound for the complexity of five-valued polarized polynomials

DOI10.1515/dma-2017-0029zbMath1406.11120OpenAlexW2763549749MaRDI QIDQ1744288

Anna Sergeevna Zinchenko, Aleksandr Sergeevich Balyuk

Publication date: 23 April 2018

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/dma-2017-0029

zbMATH Keywords

Kronecker formpolarized polynomialcomplexity lower boundsfive-valued functions

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Finite fields and commutative rings (number-theoretic aspects) (11T99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Lower bounds of complexity for polarized polynomials over finite fields

Cites Work

• Upper bounds of the complexity of functions over finite fields in some classes of Kronecker forms
• A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials
• Complexity of Boolean functions in the class of polarized polynomial forms
• On complexity of representation of multiple-valued logic functions as polarised polynomials