ECCC-Report TR17-002https://eccc.weizmann.ac.il/report/2017/002Comments and Revisions published for TR17-002en-usSat, 07 Jan 2017 21:58:35 +0200
Paper TR17-002
| Some notes on two lower bound methods for communication complexity |
Frantisek Duris
https://eccc.weizmann.ac.il/report/2017/002We 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$.Sat, 07 Jan 2017 21:58:35 +0200https://eccc.weizmann.ac.il/report/2017/002