摘要：We construct a simple function that has small unbounded-error communication
complexity in the k-party number-on-forehead (NOF) model but every probabilistic protocol
that solves it with subexponential advantage over random guessing has cost essentially
Ω(
√
n/4
k
) bits. This separates these classes up to k ≤ δ logn players for any constant
δ < 1/4, and gives the largest known separation by an explicit function in this regime of
k. Our analysis is elementary and self-contained, inspired by the methods of Goldmann,
Håstad, and Razborov (Computational Complexity, 1992). After initial publication of our
work as a preprint (ECCC, 2016), Sherstov pointed out to us that an alternative proof of an
Ω((n/4
k
)
1/7
) separation is implicit in his prior work (SICOMP, 2016). Furthermore, based
on his prior work (SICOMP, 2013 and SICOMP, 2016), Sherstov gave an alternative proof
of our constructive Ω(
√
n/4
k
) separation and also produced a stronger non-constructive
Ω(n/4
k
) separation. These results are explained in Sherstov’s preprint (ECCC, 2016) and in
article 14/22 in Theory of Computing.
关键词：complexity theory; communication complexity; weakly unbounded error;;
unbounded error; NOF model
