Super-logarithmic depth lower bounds via direct sum in communication complexity
Mauricio Karchmer, Ran Raz, Avi Wigderson · 2002
The question of whether it is easier to solve two communication problems together rather than separately is related to the complexity of the composition of Boolean functions. Based on this relationship, an approach to separating NC/sup 1 /from P is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotone NC/sup 1/ from monotone P.>