threshold functions and bounded deptii monotone circuits
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&Ohgr;( n 1/(d-1) ) size. Using this result we also get exponential lower bounds for other problems, such as connectivity and cliques.
threshold functional circuits lower bound computation size connection