Re: [theory students] Theory lunch and TCS+ talk noon tomorrow CS 2310 (Danupon Nanongkai)

[Benjamin Miller <bmiller@xxxxxxxxxxx>]

Hi all, reminder that this is happening now!

Benjamin

On Tue, Apr 24, 2018, 7:18 PM Benjamin Miller <bmiller@xxxxxxxxxxx> wrote:

Hi all,

We'll have theory lunch and tune in to the TCS+ talk at noon tomorrow in CS 2310. Danupon Nanongkai (KTH) will present "Distributed All-Pairs Shortest Paths, Exactly" (abstract below). See you there!

Benjamin

Title:ÂDistributed All-Pairs Shortest Paths, Exactly

Abstract: I will present the ~O(n^{5/4})-time distributed algorithm for computing all-pairs shortest paths exactly by Huang, Nanongkai, and Saranurak (FOCS 2017; https://arxiv.org/abs/1708.03903). The algorithm is fairly simple, and the talk will cover necessary backgrounds. I will also briefly survey recent progresses and some open problems in the field of distributed graph algorithms, where this work lies in.