• DocumentCode
    2356928
  • Title

    On rank vs. communication complexity

  • Author

    Nisan, Noam ; Wigderson, Avi

  • Author_Institution
    Inst. of Comput. Sci., Hebrew Univ., Jerusalem, Israel
  • fYear
    1994
  • fDate
    20-22 Nov 1994
  • Firstpage
    831
  • Lastpage
    836
  • Abstract
    This paper concerns the open problem of Lovasz and Saks (1988) regarding the relationship between the communication complexity of a Boolean function and the rank of the associated matrix. We first give an example exhibiting the largest gap known. We then prove two related theorems
  • Keywords
    Boolean functions; communication complexity; matrix algebra; Boolean function; associated function; associated matrix; communication complexity; deterministic communication complexity; matrix; rank; Boolean functions; Complexity theory; Computer science; Protocols;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
  • Conference_Location
    Santa Fe, NM
  • Print_ISBN
    0-8186-6580-7
  • Type

    conf

  • DOI
    10.1109/SFCS.1994.365711
  • Filename
    365711
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2356928