On complexity of computation of partial derivatives of Boolean functions realized by Zhegalkin polynomials

DOI10.1023/A:1013898304645MaRDI QIDQ1407293zbMATH OpenFDO

Authors A. N. Alekseychuk

Publication date 16 September 2003

Published in Cybernetics and Systems Analysis (Search for Journal in Brave)

zbMATH Keywords

Boolean functionsZhegalkin polynomialscombinational complexity of partial derivativesoptimal computation of partial derivativespolynomial expansions of Boolean functionsvalues of partial derivatives of Boolean functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30)

Recommendations

• On the complexity of completeness recognition of systems of Boolean functions realized in the form of Zhegalkin polynomials
• Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables
• scientific article; zbMATH DE number 3922538
• On the complexity of realization of Boolean functions by formulas
• On the complexity of realisation of Zhegalkin polynomials

Cited in

(8)

• On the complexity of completeness recognition of systems of Boolean functions realized in the form of Zhegalkin polynomials
• On the complexity of realisation of Zhegalkin polynomials
• Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables
• BOOLEAN DERIVATIVES AND COMPUTATION OF CELLULAR AUTOMATA
• scientific article; zbMATH DE number 5849341 (Why is no real title available?)
• Deterministic polynomial identity testing in non-commutative models
• Communication lower bounds using directional derivatives
• Derivation of Boolean functions by the blocks method

This page was built for publication: On complexity of computation of partial derivatives of Boolean functions realized by Zhegalkin polynomials

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