BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20220930T120000Z
UID:f61c66b250bbe5b73023d4b0ca8b769b-339
DTSTAMP:19700101T120016Z
DESCRIPTION:Negative-Weight Single-Source Shortest Paths in Near-linear Time
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/339/negative-weight-single-source-shortest-paths-in-near-linear-time/
SUMMARY:We present 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.

Organizers note: The talk is based on a paper that is the co-winner of the best paper award at FOCS 22.

For more details please visit: https://www.csa.iisc.ac.in/iisc-msr-seminar/

Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d



Hosts: Rahul Madhavan and Rameesh Paul
DTSTART:20220930T120000Z
END:VEVENT
END:VCALENDAR