This series of weekly computer science lectures take place in Robert N. Noyce ’49 Science Center 3821, with refreshments in the Computer Science Commons (Noyce 3817) 15 minutes before the event.
Thursday, Oct. 17, 2019, 4:15 p.m. “Large Scale Distributed Graph Algorithms” will be presented by Sriram Pemmaraju from The University of Iowa. 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. Techniques will be presented for the design of low-communication distributed graph algorithms, and communication complexity and information theory will be discussed for showing when such low-communication algorithms are impossible.
Pemmaraju is interested in speaking with students who are considering graduate study in computer science at The University of Iowa, including the 4-1 joint program between Grinnell and UI.