Compression Using Efficient Multicasting

and/or multicast information efficiently. However, this ability is
often overlooked when designing algorithms for these systems. In this
talk, we introduce a new compression technique that uses efficient
multicasting to significantly reduce the amount of information
communicated during multiprocessor computation, resulting in
significantly faster algorithms for Fast Fourier Transforms and
sorting on parallel models with limited bandwidth. These algorithms
demonstrate the importance of taking advantage of efficient
multicasting. The compression technique uses a new, natural variant
of Ramsey theory, which may be of independent interest.

Joint work with Tom Leighton.