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 P0 ,P1,....,Pk with links only between Pi and Pi+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 Pk. Let Dk(ƒ) be the (total) number of bits that must be exchanged to compute $f$ in worst case. Clearly, Dk (ƒ) ≤ k . D(ƒ), where D(ƒ) is the standard two-party communication complexity of ƒ. Tiwari proved that for almost all functions Dk (ƒ)- Ο(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 Dk (ƒ) 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 |