**
The Linear-Array Conjecture in
Communication Complexity is False.
**

*
Eyal Kushilevitz, Nati Linial, Rafail Ostrovsky
*

**
Abstract:
**

A * linear array* network consists of k+1 processors
P_{0 },P_{1,}....,P_{k} with links only between P_{i} and P_{i+1}
(0 ≤ i < k).
It is required to compute some boolean function ƒ(x,y)
in this network, where x is initially stored at P _{0}
and y at P_{k}. Let D_{k}(ƒ) be the (total) number of
bits that must be exchanged to compute $f$ in worst case.
Clearly, D_{k }(ƒ) ≤ k . D(ƒ), where D(ƒ) is the standard
two-party communication complexity of ƒ.
Tiwari proved that for almost all functions D_{k }(ƒ)- Ο(1) and
conjectured that this is true for * all* functions.
In this paper we disprove Tiwari's conjecture, by exhibiting an
infinite family of functions for which
D_{k }(ƒ) is essentially at most {3/4}k . D(ƒ).
This construction also leads to progress on another major problem in
this area: It is easy to bound the two-party communication complexity
of any function, given the least number of monochromatic
rectangles in any partition of the input space.
How tight are such bounds? We exhibit certain functions, for which the
(two-party) communication complexity is * twice*
larger than the best lower bound obtainable this way.

**comment:**
Preliminary version in
Proceedings of
The Twenty-Eighth ACM Symposium on Theory of Computing (STOC-96).
Journal version Accepted to COMBINATORICA.

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |