Monotone Circuits for Connectivity Require Super-Logarithmic Depth 论文

摘要

It is proved here that every monotone circuit which tests $st$-connectivity of an undirected graph on n nodes has depth $\Omega (\log^2 \,n)$. This implies a superpolynomial $(n^{\Omega (\log n)} )$ lower bound on the size of any monotone formula for $st$-connectivity. The proof draws intuition from a new characterization of circuit depth in terms of communication complexity. Within the same framework, a very simple and intuitive proof is given of a depth analogue of a theorem of Khrapchenko concerning formula size lower bounds.