Polynomial-time algorithms for checking some properties of Boolean functions given by polynomials

DOI10.1007/s00224-014-9578-0zbMath1336.68275OpenAlexW1970560920MaRDI QIDQ285507

Svetlana N. Selezneva, Anton V. Bukhman

Publication date: 19 May 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-014-9578-0

zbMATH Keywords

computational complexitypolynomial-time algorithmpolynomial representationBoolean functionlist of monomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Nonnumerical algorithms (68W05) Boolean functions (06E30)

Related Items (1)

Finding periods of Zhegalkin polynomials

Cites Work

• Unnamed Item
• Recognition of functions invariant under Moebius transformation and even functions defined in polynomial form.
• Representing Boolean functions as polynomials modulo composite numbers
• Constant depth circuits, Fourier transform, and learnability
• Algebraic Cryptanalysis
• Circuit Complexity and Multiplicative Complexity of Boolean Functions
• On the complexity of completeness recognition of systems of Boolean functions realized in the form of Zhegalkin polynomials
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Certain problems associated with Boolean polynomials

This page was built for publication: Polynomial-time algorithms for checking some properties of Boolean functions given by polynomials