The complexity of depth-3 circuits computing symmetric Boolean functions
From MaRDI portal
Publication:845823
DOI10.1016/J.IPL.2006.06.008zbMATH Open1185.68355OpenAlexW2067079998MaRDI QIDQ845823FDOQ845823
Authors: Guy Wolfovitz 
Publication date: 29 January 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2006.06.008
Recommendations
- scientific article; zbMATH DE number 1559525
- Exponential lower bounds for depth three Boolean circuits
- Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
- New upper bounds on the Boolean circuit complexity of symmetric functions
- Bounded-depth, polynomial-size circuits for symmetric functions
Cites Work
- Which problems have strongly exponential complexity?
- Title not available (Why is that?)
- Relations Among Complexity Measures
- Exponential lower bounds for depth three Boolean circuits
- Top-down lower bounds for depth-three circuits
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- A Boolean function requiring 3n network size
- An improved exponential-time algorithm for k -SAT
- The network complexity and the Turing machine complexity of finite functions
Cited In (8)
- Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
- New upper bounds on the Boolean circuit complexity of symmetric functions
- Title not available (Why is that?)
- Exponential lower bounds for depth three Boolean circuits
- On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
- Title not available (Why is that?)
- On the VC-dimension of depth four threshold circuits and the complexity of Boolean-valued functions
- Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates
This page was built for publication: The complexity of depth-3 circuits computing symmetric Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845823)
