Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR17-002 | 6th January 2017 17:52

Some notes on two lower bound methods for communication complexity

TR17-002
Authors: Frantisek Duris
Publication: 7th January 2017 21:58
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$.