KRW Composition Theorems via Lifting

Susanna F. de Rezende, Or Meir, Jakob Nordström +2

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, Raz…