Threshold functions and bounded depth monotone circuits (Q1088970)

It is shown that the n-variable majority function can be implemented on a d-level monotone circuit (with alternating levels of AND gates and OR gates, and no negated variables as inputs) requiring EXP(\(\Omega\) \(n^{1/(d-1)})\) gates, where \(\Omega\) depends on the circuit depth d. This lower bound for the size of the monotone circuit implementing the majority function establishes a size-depth trade-off and implies exponential lower bounds for many graph problems such as testing connectivity and detecting cliques and Hamiltonian cycles.