Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition

Or Meir

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}⊈{\mathbf{NC}}^1$). Karchmer, R…