• DocumentCode
    3360267
  • Title

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

  • Author

    Karchmer, Mauricio ; Raz, Ran ; Wigderson, Avi

  • Author_Institution
    MIT, Cambridge, MA, USA
  • fYear
    1991
  • fDate
    30 Jun-3 Jul 1991
  • Firstpage
    299
  • Lastpage
    304
  • Abstract
    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 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
  • Keywords
    Boolean functions; computational complexity; Boolean functions; communication complexity; direct sum; lower bounds; monotone NC1; monotone P; super logarithmic depth; Boolean functions; Circuits; Complexity theory; Distributed computing; Radio access networks; Search problems; Very large scale integration;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1991., Proceedings of the Sixth Annual
  • Conference_Location
    Chicago, IL
  • Print_ISBN
    0-8186-2255-5
  • Type

    conf

  • DOI
    10.1109/SCT.1991.160273
  • Filename
    160273
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3360267