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

Mauricio Karchmer, Ran Raz, Avi Wigderson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Scopus citations

Abstract

The question of whether it is easier to solve two communication problems together than separately is related to the complexity of the composition of Boolean functions. Based on this relationship, an approach to separating NC1 from P is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotone NC1 from monotone P.

Original languageEnglish (US)
Title of host publicationProc 6 Annu Struct Complexity Theor
PublisherPubl by IEEE
Pages299-304
Number of pages6
ISBN (Print)0818622555
StatePublished - Dec 1 1991
Externally publishedYes
EventProceedings of the 6th Annual Structure in Complexity Theory Conference - Chicago, IL, USA
Duration: Jun 30 1991Jul 3 1991

Publication series

NameProc 6 Annu Struct Complexity Theor

Other

OtherProceedings of the 6th Annual Structure in Complexity Theory Conference
CityChicago, IL, USA
Period6/30/917/3/91

All Science Journal Classification (ASJC) codes

  • Engineering(all)

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

  • Cite this

    Karchmer, M., Raz, R., & Wigderson, A. (1991). Super-logarithmic depth lower bounds via direct sum in communication complexity. In Proc 6 Annu Struct Complexity Theor (pp. 299-304). (Proc 6 Annu Struct Complexity Theor). Publ by IEEE.