The complexity of depth-3 circuits computing symmetric Boolean functions

DOI10.1016/J.IPL.2006.06.008zbMath1185.68355OpenAlexW2067079998MaRDI QIDQ845823

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Boolean function requiring 3n network size
• The network complexity and the Turing machine complexity of finite functions
• Exponential lower bounds for depth three Boolean circuits
• Which problems have strongly exponential complexity?
• Top-down lower bounds for depth-three circuits
• An improved exponential-time algorithm for k -SAT
• Relations Among Complexity Measures
• Explicit lower bound of 4.5n - o(n) for boolena circuits

This page was built for publication: The complexity of depth-3 circuits computing symmetric Boolean functions