In this paper we prove lower bounds on randomized multiparty communication
complexity, both in the \emph{blackboard model} (where each message is written
on a blackboard for all players to see) and (mainly) in the
\emph{message-passing model}, where messages are sent player-to-player. We
introduce a new technique for proving such bounds, called
\emph{symmetrization}, which is natural, intuitive, and often easy to use.
For example, for the problem where each of $k$ players gets a bit-vector of
length $n$, and the goal is to compute the coordinate-wise XOR of these
vectors, we prove a tight lower bounds of $\Omega(nk)$ in the blackboard model.
For the same problem with AND instead of XOR, we prove a lower bounds of
roughly $\Omega(nk)$ in the message-passing model (assuming $k \le n/3200$) and
$\Omega(n \log k)$ in the blackboard model. We also prove lower bounds for
bit-wise majority, for a graph-connectivity problem, and for other problems;
the technique seems applicable to a wide range of other problems as well. All
of our lower bounds allow randomized communication protocols with two-sided
error.
We also use the symmetrization technique to prove several direct-sum-like
results for multiparty communication.

本文利用对称化技术，证明了在黑板模型和消息传递模型中随机多方通信复杂性的下限，并应用该技术证明了关于多方通信的多个直接和结果。