|Computer Science/Discrete Mathematics Seminar II|
|Topic:||Graph expansion and communication complexity of algorithms|
|Affiliation:||University of California, Berkeley; von Neumann Fellow, School of Mathematics|
|Date:||Tuesday, March 18|
|Time/Room:||10:30am - 12:30pm/S-101|
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.