Threshold functions and bounded deptii monotone circuits
Ravi B. Boppana · 1984
We prove an exponential lower bound for the majority function on constant depth monotone circuits, solving an open problem of A. Yao's.. In particular, we prove that computing majority on depth d monotone circuits requires expΩ(n1/(d-1)) size. Using this result we also get exponential lower bounds for other problems, such as connectivity and cliques.