Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-079 | 11th August 2007 00:00

One-way multi-party communication lower bound for pointer jumping with applications



In this paper we study the one-way multi-party communication model,
in which every party speaks exactly once in its turn. For every
fixed $k$, we prove a tight lower bound of
$\Omega{n^{1/(k-1)}}$ on the probabilistic communication
complexity of pointer jumping in a $k$-layered tree, where the
pointers of the $i$-th layer reside on the forehead of the $i$-th
party to speak. The lower bound remains nontrivial even for $k =
(\log n)^{1/2 - \Omega(1)}$ parties. Previous to our work a lower bound was
known only for $k=3$ \cite{BabaiHayesKimmel01},
and in very restricted models for $k>3$ \cite{DJS98,Cha07}. Our
results have the following consequences to other models and
problems, extending previous work in several directions.

The one-way model is strong enough to capture {\em general} (non
one-way) multi-party protocols of bounded rounds. Thus we generalize
to this multi-party model results on two directions studied in the classical 2-party model (e.g.~\cite{PaS84,NiW93}).
The first is a round hierarchy: We give an exponential separation
between the power of $r$ and $2 r$ rounds in general
probabilistic $k$-party protocols, for any fixed $k$ and $r$. The
second is the relative power of determinism and nondeterminism: We
prove an exponential separation between nondeterministic and
deterministic communication complexity for general $k$-party
protocols with $r$ rounds, for any fixed $k,r$.

The pointer jumping function is weak enough to be a special case of the well-studied disjointness function. Thus we obtain a lower bound of
$\Omega\rb{n^{1/(k-1)}}$ on the probabilistic complexity of
$k$-set disjointness in the one-way model, which was known only
for $k=3$ parties. Our result also extends a similar lower bound
for the weaker simultaneous model, in which parties simultaneously
send one message to a referee \cite{BPSW05}.

Finally, we infer an exponential separation between the power of
different orders in which parties send messages in the one-way
model, for every fixed $k$. Previous to our work such a separation
was only known for $k=3$ \cite{NiW93}.

Our lower bound technique, which handles functions of high
discrepancy, may be of independent interest. It provides a
``party-elimination'' induction, based on a restricted form of a
direct-product result, specific to the pointer jumping function.

ISSN 1433-8092 | Imprint