KRW Composition Theorems via Lifting
KRW Composition Theorems via Lifting
One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., P\nsubseteq NC <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> ). Karchmer, Raz, and Wigderson [13] suggested to approach this problem by proving that depth complexity behaves "as expected" with respect to the composition of …