Theory of Computing
-------------------
Title     : On Multiparty Communication with Large versus Unbounded Error
Authors   : Alexander A. Sherstov
Volume    : 14
Number    : 22
Pages     : 1-17
URL       : https://theoryofcomputing.org/articles/v014a022

Abstract
--------

The _unbounded-error_ communication complexity of the Boolena
function $F$ is the limit of the $\epsilon$-error randomized
complexity of $F$ as $\epsilon\to1/2.$ Communication complexity with
 _weakly unbounded error_ is defined similarly but with an additive
penalty term that depends on $1/2-\epsilon$. Explicit functions are
known whose two-party communication complexity with unbounded error
is logarithmic compared to their complexity with weakly unbounded error. 
Chattopadhyay and Mande (ECCC TR16-095, Theory of Computing 2018) 
recently generalized this exponential separation to the 
number-on-the-forehead multiparty model. We show how to derive such 
an exponential separation from known two-party work, achieving a 
quantitative improvement along the way. We present several proofs here,
some as short as half a page.

In more detail, we construct a $k$-party communication problem
$F\colon(\{0,1\}^{n})^{k}\to\{0,1\}$ that has complexity $O(\log n)$
with unbounded error and $\Omega(\sqrt n/4^{k})$ with weakly unbounded
error, reproducing the bounds of Chattopadhyay and Mande. In addition,
we prove a quadratically stronger separation of $O(\log n)$ versus
$\Omega(n/4^k)$ using a nonconstructive argument.

A preliminary version of this paper appeared in ECCC, TR16-138, 2016.