Bellman-Ford in Almost-Linear Time for Dense Graphs

Start Date: February 25, 2026
Event Start Time: 11:00 AM
Event End Time: 12:00 PM
Seminar Series: Theoretical Computer Science Seminar
Presenter(s): George Li - Carnegie Mellon University
Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
Presentation Type: Stand Alone Presentation
Abstract:
I will present an n^2 time algorithm for single-source shortest paths with negative real weights, building on the breakthrough work of Fineman (STOC 2024). The talk will be entirely self-contained, and only assume basic probability facts.

Based on joint work with Jason Li, Satish Rao, and Junkai Zhang.

Events