Title: The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions.
Abstract: We give tight lower bounds for the size of depth-3 circuits with limited bottom fanin computing symmetric Boolean functions. We show that any depth-3 circuit with bottom fanin k which computes the Boolean function Exactn/(k+1)n, has at least (1 + 1/k)n/(n + 1) gates. We show that for k = o(√n) this lower bound is essentially tight, by generalizing a known upper bound on the size of depth-3 circuits with bottom fanin 2, computing symmetric Boolean functions.
Publication Year: 2006
Publication Date: 2006-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot