Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-002 | 6th January 2017 17:52

Some notes on two lower bound methods for communication complexity

RSS-Feed




TR17-002
Authors: Frantisek Duris
Publication: 7th January 2017 21:58
Downloads: 2888
Keywords: 


Abstract:

We compare two methods for proving lower bounds on standard two-party model of communication complexity, the Rank method and Fooling set method. We present bounds on the number of functions f(x,y), x,y\in\{0,1\}^n, with rank of size k and fooling set of size at least k, k\in [1,2^n]. Using these bounds we give a novel proof that almost all Boolean functions f are hard, i.e., the communication complexity of f is greater than or equal to n, using the field \mathbb{Z}_2.



ISSN 1433-8092 | Imprint