Seminar series
Date
Thu, 13 Mar 2014
Time
16:00 -
17:00
Location
L6
Speaker
Olga Holtz
Organisation
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.