Expanders and Communication-Avoiding Algorithms

Video of this lecture

COMPUTER SCIENCE/DISCRETE MATH I
Topic:	Expanders and Communication-Avoiding Algorithms
Speaker:	Oded Schwartz
Affiliation:	Technical University Berlin
Date:	Monday, January 25
Time/Room:	11:15am - 12:15pm/S-101

---

Algorithms spend time on performing arithmetic computations, but often more on moving data, between the levels of a memory hierarchy and between parallel computing entities. Judging by the hardware evolution of the last few decades, the fraction of running time spent on communication is expected to increase, and with it - the demand for communication-avoiding algorithms. We use geometric, combinatorial, and algebraic ideas and techniques, some of which are known in the context of expander graphs, to construct provably communication-optimal algorithms.