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.
complexity of the function is the minimum number of bits
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