• DocumentCode
    3766016
  • Title

    On the communication complexity of greater-than

  • Author

    Sivaramakrishnan Natarajan Ramamoorthy;Makrand Sinha

  • Author_Institution
    Computer Science and Engineering, University of Washington, USA
  • fYear
    2015
  • Firstpage
    442
  • Lastpage
    444
  • Abstract
    We give a simple information theoretic proof that the public-coin randomized communication complexity of the greater-than function is Ω(logn) for bit-strings of length n.
  • Keywords
    "Protocols","Complexity theory","Boolean functions","Mutual information","Random variables","Context","Markov processes"
  • Publisher
    ieee
  • Conference_Titel
    Communication, Control, and Computing (Allerton), 2015 53rd Annual Allerton Conference on
  • Type

    conf

  • DOI
    10.1109/ALLERTON.2015.7447037
  • Filename
    7447037
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3766016