One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, a.k.a, the \mathbf{P} versus \mathbf{NC^1} problem. The current best depth lower bound is (3-o(1))\cdot \log n, and it is widely open how to prove a super-3\log n depth lower bound. ... more >>>