Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-139 | 25th August 2015 23:58

Lower bound for communication complexity with no public randomness

RSS-Feed




TR15-139
Authors: Eli Ben-Sasson, Gal Maor
Publication: 25th August 2015 23:59
Downloads: 872
Keywords: 


Abstract:

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 first 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.



ISSN 1433-8092 | Imprint