期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
