Jason Li: Deterministic Padded Decompositions and Negative-Weight Shortest Paths

Описание: CMU Theory Lunch Talk

Speaker: Jason Li

Date: 01/28/2026

Title: Deterministic Padded Decompositions and Negative-Weight Shortest Paths

Abstract: A recent breakthrough of Bernstein, Nanongkai, and Wulff-Nilsen established the first near-linear time algorithm for negative-weight single source shortest paths on integer-weighted graphs. We refine their approach and obtain the first near-linear time deterministic algorithm for the problem. Our main ingredient is a deterministic construction of a padded decomposition on directed graphs, which may be of independent interest.

The talk will present the entire algorithm and proof at the level of a graduate algorithms class.