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

DOI10.1007/S00224-014-9578-0MaRDI QIDQ285507zbMATH OpenOpenAlexFDO

Authors 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 complexityBoolean functionpolynomial-time algorithmlist of monomialspolynomial representation

Mathematics Subject Classification ID

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

Recommendations

• Properties of polynomials of periodic functions and the complexity of periodicity detection by the Boolean function polynomial
• Certain problems associated with Boolean polynomials
• Multiaffinity testing of Boolean functions using their Zhegalkin polynomials
• On the complexity of completeness recognition of systems of Boolean functions realized in the form of Zhegalkin polynomials
• scientific article; zbMATH DE number 2108196

Cites work

• Algebraic Cryptanalysis
• Boolean functions in coding theory and cryptography. Translated from the Russian by Svetla Nikova
• Certain problems associated with Boolean polynomials
• Circuit complexity and multiplicative complexity of Boolean functions
• Constant depth circuits, Fourier transform, and learnability
• On the complexity of completeness recognition of systems of Boolean functions realized in the form of Zhegalkin polynomials
• Recognition of functions invariant under Moebius transformation and even functions defined in polynomial form.
• Representing Boolean functions as polynomials modulo composite numbers
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

Cited in

(6)

• Properties of polynomials of periodic functions and the complexity of periodicity detection by the Boolean function polynomial
• Finding periods of Zhegalkin polynomials
• scientific article; zbMATH DE number 1421070 (Why is no real title available?)
• Algorithms for synthesis of polynomials implementing weakly specified Boolean functions and systems
• A Polynomial-Time Algorithm to Check Closedness of Simple Second Order Mixed-Integer Sets
• Multiaffinity testing of Boolean functions using their Zhegalkin polynomials

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

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