Danupon Nanongkai: Distributed Shortest Paths, Exactly
09 April 2018 - 09 April 2018
Manno, Galleria 1, 2nd floor, room G1-204 @12:00
This talk concerns the problem of quickly computing distances and
shortest paths on distributed networks (the CONGEST model). There have
been many developments for this problem in the last few years,
resulting in tight approximation schemes. This left widely open
whether exact algorithms can perform equally well. In this talk, we
will discuss some recent progress in answering this question. The talk
will focus on surveying the state of the art, and will discuss some
recent algorithms in details as time permits.

Based on joint work with Chien-Chung Huang and Thatchaphol Saranurak
(FOCS 2017) and with Sebastian Krinninger (work in progress).

The speaker

 Danupon Nanongkai is currently an associate professor in the School of Electrical Engineering and Computer Science (EECS), KTH Royal
Institute of Technology, Sweden. He received a Ph.D. in Algorithms,
Combinatorics, and Optimization (ACO) from Georgia Tech, USA, in 2011 and a docent in Computer Science from KTH in 2017. He was a recipient of the Principles of Distributed Computing Doctoral Dissertation Award in 2013 and the ERC Starting Grant in 2017. His research interest is generally on graph algorithms and particularly on distributed, dynamic, and approximation graph algorithms.

Registration is highly recommended

 Pizza (or alternative food) and drinks will be offered
at the end of the talk. If you plan to attend, please register in a
timely fashion at the following link so that we will have no shortage of food.