Direct Sum Questions in Classical Communication Complexity
Denis Yu. Pankratov · 2012
In 1988, Karchmer and Wigderson generalized Yao’s two-party communication model of functions to relations and showed a remarkable connection of this model to the Boolean circuit model. A few years later, continuing this line of work, Karchmer, Raz, and Wigderson proposed a program to separate NC from P through direct-sum-type inequalities in communication complexity. This spurred the study of this fundamental question in communication complexity: given problems A and B, is it easier to solve A and B together than separately? It seems that we are still far from separating NC from P ; however, during the last 20 years of research our knowledge of the behavior of dierent communication complexity measures with respect to the direct sum has seen a lot of progress. We survey some of these results and make a new observation about the recent approach to the direct-sum question in the randomized setting.