Computational Mathematics 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.

Synopsis:

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.