[Talks@IDSIA] PIDSIA Seminar by Danupon Nanongkai

Speaker: Danupon Nanongkai, KTH Royal Institute of Technology Title: Distributed Shortest Paths, Exactly Abstract: 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). Bio: 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. When: Monday 9th of April 2018, 12:00-13:00 Location: Manno, Galleria 1, 2nd floor, room G1-204 Registration: 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: https://doodle.com/poll/6qp9hc99m5p42gw5