The linear-array conjecture in communication complexity is false

A linear array network consists of k+1 processors P-0, P-1,...,P-k with lin ks only between P-i and Pi+1 (0 less than or equal to i < k). It is require d to compute some boolean function f(x,y) in this network, where initially x is stored at P-0 and y is stored at P-k. Let D-k(f) be the (total) number of bits that must be exchanged to compute f in worst case. Clearly, D-k(f) less than or equal to k.D(f), where D(f) is the standard two-party communi cation complexity of f. Tiwari proved that for almost all functions D-k(f) greater than or equal to k(D(f) -O(1)) and conjectured that this is true fo r all functions. In this paper we disprove Tiwari's conjecture, by exhibiting an infinite fa mily of functions for which D-k(f) is essentially at most 3/4k.D(f). Our co nstruction also leads to progress on another major problem in this area: It is easy to bound the two-party communication complexity of any function, g iven the least number of monochromatic rectangles in any partition of the i nput space. How tight are such bounds? We exhibit certain functions, for wh ich the (two-party) communication complexity is twice as large as the best lower bound obtainable this way.