Dr. Ohad Trabelsi - New Developments in Fine-Grained Complexity

Fine-grained complexity has emerged in the last decade as a powerful tool for understanding the computational limits of problems in P.
By linking a few key hardness assumptions to a broad range of problems, this tool provides a systematic approach to addressing longstanding challenges in algorithm design.
In this lecture, I will explore fine-grained complexity, primarily as a guide to faster algorithms-highlighting recent advances in the Gomory-Hu problem, along with progress on a few other related topics.