UC Berkeley & TU Berlin

I will discuss a novel approach to estimating communication costs of an algorithm (also known as its I/O complexity), which is based on small-set expansion for computational graphs. Various applications and implications will be discussed as well, mostly having to do with linear algebra algorithms. This includes, in particular, first known (and tight) bounds on communication complexity of fast matrix multiplication.

Joint work with Grey Ballard, James Demmel, Benjamin Lipshitz and Oded Schwartz.