AG 1   Info

AG Audience

English

90 Minutes

Saarbrücken

I will discuss the paper of the same title which can be found here: https://arxiv.org/abs/2203.03456 (see the abstract below). This paper presents a randomized algorithm that computes single-source shortest paths (SSSP) in O(m log^8(n) log W) time when edge weights are integral and can be negative and are >=-W. This essentially resolves the classic negative-weight SSSP problem. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools.

In the first 30 minutes, I will introduce the problem and some key ideas. After a short break, I will discuss the main technical ideas: (i) low-diameter decomposition (LDD) and (ii) how to use it. Each of the two technical parts will take about 30 minutes.

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

527 278 8807

passcode not visible

logged in users only

The talk will take place in the hybrid format. The in-person participants will meet in room 024 at E1 4 and the online participants can meet via the zoom link given above. If you wish to attend the talk online and do not have the password for the zoom room, please contact Roohani Sharma at rsharma@mpi-innf.mpg.de.