Graph Expansion and Communication Costs of Algorithms

TitleGraph Expansion and Communication Costs of Algorithms
Publication TypeJournal Article
Year of Publication2013
AuthorsBallard, G., Demmel J., Holtz O., & Schwartz O.
Abstract

The communication complexity of algorithms is shown to be closely related to the expansion properties of the corresponding computation graphs. We demonstrate this on Strassen’s fast matrix multiplication algorithm, and obtain the first lower bound on its communication cost. This bound is optimal.

AttachmentSize
BallardDemmelHoltzSchwartz.pdf253.83 KB