Communication complexity towards lower bounds on circuit depth

Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC(1). They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-m) circuit for this problem requires dk is an element of Omega(log(2) n/log log n) depth. This would separate AC(1) from NC1. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem which they call the Universal Composition Relation. We give an almost optimal lower bound of dk - O(d(2) (k log k)(1/2)) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function on k bits requiring Omega(k) circuit depth. Although this fact can be easily established using a counting argument, we hope. that the ideas in our proof will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds.