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

DOI10.1007/S10598-013-9166-1MaRDI QIDQ895458zbMATH OpenOpenAlexFDO

Authors 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 boundBoolean functioncircuitpolynomialcircuit complexity

Mathematics Subject Classification ID

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

Recommendations

• Circuit complexity and multiplicative complexity of Boolean functions
• On the complexity of realizing the powers of a Boolean \((n,n)\)-function
• On complexity of computation of partial derivatives of Boolean functions realized by Zhegalkin polynomials
• On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\).
• On bounds for complexity of circuits of multi-input functional elements

Cites work

• scientific article; zbMATH DE number 3133387 (Why is no real title available?)
• scientific article; zbMATH DE number 3873237 (Why is no real title available?)
• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 5242388 (Why is no real title available?)
• 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\)
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen

Cited in

(6)

• Explicit lower bound of 4.5n - o(n) for boolena circuits
• On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
• scientific article; zbMATH DE number 1222575 (Why is no real title available?)
• Cancellation-free circuits in unbounded and bounded depth
• On complexity of computation of partial derivatives of Boolean functions realized by Zhegalkin polynomials
• scientific article; zbMATH DE number 4047102 (Why is no real title available?)

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

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