Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables
DOI10.1007/S10598-013-9166-1zbMATH Open1333.94077OpenAlexW2014915490MaRDI QIDQ895458FDOQ895458
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
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A fast algorithm for the construction of polynomials modulo \(k\) for \(k\)-valued functions for composite \(k\)
- Title not available (Why is that?)
- A class of Boolean functions with linear combinational complexity
Cited In (6)
- On complexity of computation of partial derivatives of Boolean functions realized by Zhegalkin polynomials
- Title not available (Why is that?)
- Cancellation-free circuits in unbounded and bounded depth
- 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
- Title not available (Why is that?)
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)
