DIMACS Theory of Computing Seminar


Intelligent Relays Can Hep in Communication Complexity


Nathan Linial
Hebrew University, Jerusalem


DIMACS Seminar Room 431, CoRE Building
Busch Campus, Rutgers University


4:30 PM
Thursday, November 9, 1995


In the communication complexity model, two processors each posessing some information, must jointly compute some function that depends on this information. The obvious way to do this is for one processor to send the other its information and let the other compute the function, but it may be possible to compute the function with much less communication. The communication complexity of the function is the minimum number of bits of communication needed in worst case to compute the function.

Consider a situation where the two processors are not connected directly, but are linked by a path with k intermediate processors a network of processors. Trivially, the intermediate processors can be used as passive relays, and thus the communication required increases by at most a factor of k+1. Tiwari conjectured that for any function, this increase is unavoidable. Here we refute this conjecture by presenting an infinite family of functions for which the communication complexity with one intermediate processor is less than twice the ``direct'' communication complexity.

This is joint work with Eyal Kushilevitz and Rafi Ostrovsky.

Document last modified on November 3, 1995