The complexity of depth-3 circuits computing symmetric Boolean functions
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 Exact(n)(/(k+l)')(n) has at least (1 + 1/k)(n)/(n + 1) gates. We show that for k = o(root 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. (c) 2006 Elsevier B.V. All rights reserved.
depth-3 circuits computational complexity theory of computation