Theory of Computing
-------------------
Title : On Multiparty Communication with Large versus Unbounded Error
Authors : Alexander A. Sherstov
Volume : 14
Number : 22
Pages : 1-17
URL : http://www.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.