Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NOF MODEL:
Reports tagged with NOF Model:
TR16-095 | 7th June 2016
We show that a simple function has small unbounded error communication complexity in the $k$-party number-on-forehead (NOF) model but every probabilistic protocol that solves it with sub-exponential advantage over random guessing has cost essentially $\Omega\left(\frac{\sqrt{n}}{4^k}\right)$ bits. Such a separation was first shown for $k=2$ independently by Buhrman et al. ['07] ... more >>>