Title :
On the communication complexity of greater-than
Author :
Sivaramakrishnan Natarajan Ramamoorthy;Makrand Sinha
Author_Institution :
Computer Science and Engineering, University of Washington, USA
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"
Conference_Titel :
Communication, Control, and Computing (Allerton), 2015 53rd Annual Allerton Conference on
DOI :
10.1109/ALLERTON.2015.7447037
