__
TR07-079 | 11th August 2007 00:00
__

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

TR07-079
Authors:

Emanuele Viola,

Avi Wigderson
Publication: 14th August 2007 12:45

Downloads: 1870

Keywords:

Communication complexity,

disjointness,

lower bound,

multiparty,

nondeterminism,

one-way,

order,

pointer jumping,

round,

separation,

streaming algorithm
**Abstract:**
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.