We give a self contained proof of a logarithmic lower bound on the communication complexity of any non redundant function, given that there is no access to shared randomness. This bound was rst stated in Yao’s seminal paper [STOC 1979], but no full proof appears in the literature. Our proof uses the method of Babai and Kimmel [Computational Complexity 1997], introduced there in the context of the simultaneous messages model, applying it to the more general and standard communication model of Yao.
['Eli Ben-Sasson', 'Gal Maor']
Lower bound for communication complexity with no public randomness