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: 2620
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