Super-logarithmic depth lower bounds via the direct sum in communication complexity

Mauricio Karchmer, Ran Raz, Avi Wigderson

Research output: Contribution to journalArticlepeer-review

76 Scopus citations


Is it easier to solve two communication problems together than separately? This question is related to the complexity of the composition of boolean functions. Based on this relationship, an approach to separating NC 1 from P is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotone NC 1 from monotone P.

Original languageEnglish (US)
Pages (from-to)191-204
Number of pages14
JournalComputational Complexity
Issue number3-4
StatePublished - Sep 1 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Super-logarithmic depth lower bounds via the direct sum in communication complexity'. Together they form a unique fingerprint.

Cite this