Doctoral Speaking Skills Talk - George Li

September 30, 2026  12:00PM—1:00PM

Location:
6501 - Gates and Hillman Centers

Speaker:
GEORGE LI, Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://sites.google.com/view/gzli929/home

Bellman-Ford in Almost-Linear Time

In this talk we consider a new algorithm for the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in `m^{1+o(1)}` time.

This improves the classic Bellman-Ford algorithm taught in undergraduate courses, which runs in `O(mn)` time.

Presented as part of the Theory Lunch Seminar

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement

Contact
Matt Stewart

Add event to Google
Add event to iCal