Computer Science/Discrete Mathematics Seminar II | |

Topic: | Graph expansion and communication complexity of algorithms |

Speaker: | Olga Holtz |

Affiliation: | University of California, Berkeley; von Neumann Fellow, School of Mathematics |

Date: | Tuesday, March 18 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Video Link: | https://video.ias.edu/csdm/2014/0318-OlgaHoltz |

In joint work with Ballard, Demmel, and Schwartz, we showed the communication cost of algorithms (also known as I/O-complexity) to be closely related to the small-set expansion properties of the corresponding computation graphs. This graph expansion approach produces first lower bounds on the communication costs of Strassen's and other fast matrix multiplication algorithms. I will discuss both the general method and its concrete implementations.