Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with NOF Model:
TR16-095 | 7th June 2016
Arkadev Chattopadhyay, Nikhil Mande

Small Error Versus Unbounded Error Protocols in the NOF Model

Revisions: 1 , Comments: 1

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

ISSN 1433-8092 | Imprint