TR96-063 Authors: Martin Dietzfelbinger

Publication: 12th December 1996 17:54

Downloads: 2433

Keywords:

Tiwari (1987) considered the following scenario: k+1 processors P_0,...,P_k,

connected by k links to form a linear array, compute a function f(x,y), for

inputs (x,y) from a finite domain X x Y, where x is only known to P_0 and

y is only known to P_k; the intermediate processors P_1,...,P_{k-1} initially

do not have any information. The processors compute f(x,y) by exchanging

binary messages across the links according to some protocol. Let D_k(f) denote

the minimal complexity of such a protocol, i.e., the total number of bits

sent across all links for the worst case input, and let D(f) = D_1(f) denote

the (standard) two-party communication complexity of f.

Tiwari proved that D_k(f) >= k*(D(f)-O(1)) for almost all functions,

and conjectured this to be true for all f. His conjecture was falsified

by Kushilevitz, Linial, and Ostrovsky (1996): they exhibited a function f

for which D_k(f) is essentially bounded above by 0.75*D(f). The best known

general lower bound known is D_k(f) >= k*(D(f)^(1/2)-log k-3). --- We prove:

D_k(f) >= 0.146 * k * D(f), for all functions f and all k >= 2.

Applying the general framework provided by Tiwari, one may derive lower bounds

for the communication complexity of a function in general asynchronous

networks in terms of its two-party communication complexity.

Moreover, resolving a longstanding open question, the result shows that

the communication complexity of a function directly implies a lower bound

for the running time of one-tape Turing machines computing this function. ---

The nondeterministic and the randomized case are also studied, leading to

similar results.