Lower bounds of complexity for polarized polynomials over finite fields

DOI10.1134/S0037446619010014MaRDI QIDQ2002473zbMATH OpenOpenAlexWikidataFDO

Authors Aleksandr Sergeevich Baliuk, Anna Sergeevna Zinchenko

Publication date 12 July 2019

Published in Siberian Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0037446619010014

zbMATH Keywords

finite fieldlower bound of complexitypolarized polynomial

Mathematics Subject Classification ID

Boolean functions (06E30) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Boolean functions (94D10)

Recommendations

• Lower bounds for the complexity of polynomials
• scientific article; zbMATH DE number 619540
• Lower bound of the complexity of functions over a finite field of order 4 in the class of polarized polynomials
• On upper bounds of the complexity of functions over nonprime finite fields in some classes of polarized polynomials
• STACS 2005
• A Lower Bound on the Complexity of Polynomial Multiplication over Finite Fields
• On lower bounds for the complexity of polynomials and their multiples
• Complexity of function systems over a finite field in the class of polarized polynomial forms
• Polynomial evaluation over finite fields: new algorithms and complexity bounds
• True complexity of polynomial progressions in finite fields

Cites work

• A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials
• A proof of a conjecture by Schweizer on the Drinfeld modular polynomial \(\varPhi _T(X,Y)\)
• Complexity of Boolean functions in the class of polarized polynomial forms
• scientific article; zbMATH DE number 3882549 (Why is no real title available?)
• Lower bound for the complexity of five-valued polarized polynomials
• Minimization of Exclusive or and Logical Equivalence Switching Circuits
• On complexity of representation of multiple-valued logic functions as polarised polynomials
• On upper bounds of the complexity of functions over nonprime finite fields in some classes of polarized polynomials
• Reed-Muller Like Canonic Forms for Multivalued Functions
• Upper bounds of the complexity of functions over finite fields in some classes of Kronecker forms

Cited in

(12)

• On polynomials with symmetric Galois group which are easy to compute
• On lower bounds for the complexity of polynomials and their multiples
• Complexity of function systems over a finite field in the class of polarized polynomial forms
• Lower bound for the complexity of five-valued polarized polynomials
• Lower bound of the complexity of seven-valued functions in the class of polarized polynomials
• Lower bounds for the complexity of polynomials
• Complexity lower bound for Boolean functions in the class of extended operator forms
• On upper bounds of the complexity of functions over nonprime finite fields in some classes of polarized polynomials
• On upper bound of the complexity of quasi polynomial representations of functions over finite fields
• Upper bounds of the complexity of functions over finite fields in some classes of Kronecker forms
• Lower bound of the complexity of functions over a finite field of order 4 in the class of polarized polynomials
• A Lower Bound on the Complexity of Polynomial Multiplication over Finite Fields

This page was built for publication: Lower bounds of complexity for polarized polynomials over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2002473)