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+1))~n, has at least (1 + 1/k)~n /(n + 1) gates. We show that for k = o(n~(1/2)) 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.