Numerical Analysis and Scientific Computing Seminar
Graph Expansion and Communication Complexity of Algorithms
Speaker: Olga Holtz, UC Berkeley, TU-Berlin and IAS
Location: Warren Weaver Hall 1302
Date: Feb. 28, 2014, 10 a.m.
I will present an overview of recently developed methods to analyze communication costs of algorithms (also known as I/O-complexity). Our main results connect communication complexity and small-set expansion properties of the corresponding computation graphs. This will be demonstrated on several classes of algorithms (most notably fast matrix multiplication), leading to novel lower bounds on their communication costs. Joint work with Grey Ballard, James Demmel, Benjamin Lipshitz, and Oded Schwartz.