Coursera Spring Sale
40% Off Coursera Plus Annual!
Grab it
Explore a groundbreaking computer science seminar that examines the fundamental differences between two classic algorithmic problems: All-Pairs Min-Cut and All-Pairs Shortest-Path. Delve into the All-Pairs Min-Cut problem (APMC), which computes minimum cuts between all node pairs in a graph, and discover how the remarkable 1961 Gomory-Hu algorithm requiring only n-1 calls has dominated the field for over 60 years with its cubic time bound. Compare this with the seemingly similar All-Pairs Shortest-Path problem (APSP) that computes distances rather than connectivity, and understand how APSP's conjectured cubic complexity has become central to fine-grained complexity theory, establishing conditional lower bounds for numerous fundamental problems. Learn about recent breakthrough research that finally breaks the 60-year-old cubic barrier for APMC, establishing a surprising separation between these two problems and challenging long-held assumptions in the field. Gain insights into cutting-edge techniques including expander decompositions, regularity lemmas, and theorems from additive combinatorics that enable these advances, while exploring how this work opens new approaches to attacking the APSP conjecture and reshapes our understanding of fundamental algorithmic complexity.
