Technical Report CS0870

TR#:CS0870
Class:CS
Title: THE LINEAR-ARRAY CONJECTURE OF COMMUNICATION COMPLEXITY IS FALSE.
Authors: E. Kushilevitz, N. Linial and R. Ostrovsky
PDFNot Available
Abstract: Consider a network of $k+1$ processors connected by $k$ links in a {\em linear array}. The processors wish to compute some boolean function $f(x,y)$ where each of $x$ and $y$ is stored in one of the end-processors of the array. Let $D_k(f)$ be the (total) number of bits that must be exchanged to compute $f$. Clearly, $D_k(f) \leq k \cdot D(f)$, where $D(f)$ is the standard two party communication complexity of $f$. Tiwari proved that for almost all functions $D_k(f) \geq k (D(f) - O(1))$ and conjectured that this is true for all functions. In this paper we disprove Tiwari's conjecture by exhibiting a function for which $D_k(f)$ is essentially at most $\frac{3}{4}k \cdot D(f)$. Using our result we also get some progress on another important problem in communication complexity: How good are lower bounds proved by giving lower bounds on the number of monochromatic rectangles required to partition the space of inputs. We show that for certain functions the (two-party) communication complexity may be 2 times larger than the best lower bound obtained this way.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1995/CS/CS0870), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1995
To the main CS technical reports page

Computer science department, Technion
admin