A nearly-$4\log n$ depth lower bound for formulas with restriction on top

Hao Wu

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{N}{\mathbf{C}}^1$ pr…