Computer Science NASC Seminar

Graph Expansion and Communication Complexity of Algorithms

Olga Holtz, UC Berkeley, TU-Berlin and IAS

February 28, 2014 10:00AM
Warren Weaver Hall, Room 1302
251 Mercer Street
New York, NY, 10012-1110

Spring 2014 NASC Seminars Calendar


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.

top | contact webmaster