Computer Science/Discrete Mathematics Seminar I

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits. Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested approaching this problem by proving that depth complexity of a composition of two functions is roughly the sum of their individual depth complexities. They showed that the validity of this conjecture would imply the desired lower bounds.

The intuition that underlies the KRW conjecture is that composition should behave like a "direct-sum problem", in a certain sense, and therefore the depth complexity of the composition should be the sum of the individual depth complexities. Nevertheless, there are two obstacles toward turning this intuition into a proof: first, we do not know how to prove that the composition must behave like a direct-sum problem; second, we do not know how to prove that the complexity of the latter direct-sum problem is indeed the sum of the individual complexities.

In this talk, we will describe a new work that tackles the second obstacle. We will consider a notion of "strong composition" that is forced to behave like a direct-sum problem, and see that a variant of the KRW conjecture holds for this notion. This result demonstrates that the first obstacle above is the crucial barrier toward resolving the KRW conjecture. Along the way, we will discuss some general techniques that might be of independent interest.