Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables

DOI10.1007/S10598-013-9166-1zbMath1333.94077OpenAlexW2014915490MaRDI QIDQ895458

Svetlana N. Selezneva

Publication date: 3 December 2015

Published in: Computational Mathematics and Modeling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10598-013-9166-1

zbMATH Keywords

lower boundpolynomialcircuitBoolean functioncircuit complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Cancellation-free circuits in unbounded and bounded depth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• A class of Boolean functions with linear combinational complexity
• A fast algorithm for the construction of polynomials modulo k for k-valued functions for composite k

This page was built for publication: Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables