Graph Expansion and Communication Costs of Algorithms
|Title||Graph Expansion and Communication Costs of Algorithms|
|Publication Type||Journal Article|
|Year of Publication||2013|
|Authors||Ballard, G., Demmel J., Holtz O., & Schwartz O.|
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.