Threshold functions and bounded depth monotone circuits

摘要

We prove an exponential lower bound for the majority function on constant depth monotone circuits, solving an open problem posed by Yao (in “Proceedings of 24th IEEE Sympos. Found. of Comput. Sci.,” Tucson, 1983, pp. 420–428). In particular, we prove that computing majority on depth d monotone circuits requires exp Ω(n1(d−1)) size. This result implies exponential lower bounds for other functions, such as testing connectivity and detecting cliques in graphs.