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

DOI10.1023/A:1013898304645zbMATH Open1024.06007MaRDI QIDQ1407293FDOQ1407293

A. N. Alekseychuk

Publication date: 16 September 2003

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

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

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)

Cited In (6)

• 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
• BOOLEAN DERIVATIVES AND COMPUTATION OF CELLULAR AUTOMATA
• Title not available (Why is that?)
• Deterministic polynomial identity testing in non-commutative models
• Communication Lower Bounds Using Directional Derivatives

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)