Danupon Nanongkai: Distributed graph algorithms and lower bounds

Practicalities

Lunch is served at 12:00 noon (register at this doodle at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

Abstract

This talk will focus on distributed approximation algorithms for solving basic graph problems such as shortest paths, minimum spanning trees, and minimum cut. I will cover:

• Survey of the recent progress.
• Open problems and some related conjectures.
• A basic technique for proving lower bounds by a reduction from two-party communication complexity based on [1].

If time permits, I will touch some algorithmic techniques as well (e.g. [2,3]). No background in distributed algorithms will be assumed in this talk.

References

[1] Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer: Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput. 41(5): 1235-1265 (2012)

[2] Danupon Nanongkai: Distributed Approximation Algorithms for Weighted Shortest Paths. STOC 2014: 565-573

[3] Danupon Nanongkai, Hsin-Hao Su: Almost-Tight Distributed Minimum Cut Algorithms. DISC 2014: 439-453