The complexity of depth-3 circuits computing symmetric Boolean functions

DOI10.1016/J.IPL.2006.06.008MaRDI QIDQ845823zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational complexitytheory of computationdepth-3 circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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

• scientific article; zbMATH DE number 3133387 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 1452705 (Why is no real title available?)
• scientific article; zbMATH DE number 1929951 (Why is no real title available?)
• A Boolean function requiring 3n network size
• An improved exponential-time algorithm for k -SAT
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Exponential lower bounds for depth three Boolean circuits
• Relations Among Complexity Measures
• The network complexity and the Turing machine complexity of finite functions
• Top-down lower bounds for depth-three circuits
• Which problems have strongly exponential complexity?

Cited in

(8)

• New upper bounds on the Boolean circuit complexity of symmetric functions
• scientific article; zbMATH DE number 1559525 (Why is no real title available?)
• Exponential lower bounds for depth three Boolean circuits
• scientific article; zbMATH DE number 3968581 (Why is no real title available?)
• On the VC-dimension of depth four threshold circuits and the complexity of Boolean-valued functions
• Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
• Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates
• On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

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)