KRW Composition Theorems via Lifting
One of the major open problems in complexity theory is proving super-logarithmiclower bounds on the depth of circuits (i.e., P⊈NC1). Karchmer et al. (Comput Complex 5(3/4):191–204, 1995) suggested to approach thisproblem by proving that depth complexity behaves “as expected”with respect to the composition of functions f◊g. They showedthat the validity of this conjecture would imply that P⊈NC1.Seve