Computer Science Events

Oct 24

CS Tea Talk: Large Scale Distributed Graph Algorithms

CS Tea Talk: Sriram Pemmaraju from the University of Iowa is our featured speaker.

4:00 – 5:00 pm / CMC 301

As graphs become enormous (e.g., the Facebook "friends" graph has a trillion edges!), it is becoming impossible to solve large-scale algorithmic graph problems on a single machine. This talk focuses on distributed graph algorithms, where the input graph is split into pieces and distributed across many machines. In this setting communication is the costliest resource and so machines need to communicate just enough with other machines to ensure correctness, but no more. I will present algorithmic techniques for the design of low-communication distributed graph algorithms. I will also present techniques from communication complexity and information theory for showing when such low-communication algorithms are impossible. We will begin with tea and cookies in CMC 328 and then move to CMC 301 for our talk.

Sponsored by Computer Science Events. Contact: Paula Stowe, x5748