Amir Abboud of the Weizmann Institute of Science presents a Computer Science/Discrete Mathematics seminar at the Institute for Advanced Study on two classic graph problems. The All-Pairs Min-Cut problem has stood at a cubic time barrier since Gomory and Hu's 1961 algorithm, which uses n-1 single-pair min-cut calls to build a cut-equivalent tree preserving all pairwise minimum cuts. Abboud contrasts this with All-Pairs Shortest-Path, where the conjecture that cubic time is essentially required has driven a decade of fine-grained complexity results. He walks through a sequence of his own papers, with coauthors including Krauthgamer, Li, Panigrahi, Saranurak, and Trabelsi, that finally break the 60-year cubic barrier for min-cut while proving a surprising separation between the two problems. The talk explains the technical tools behind the breakthrough, including expander decompositions, regularity lemmas, and results borrowed from additive combinatorics.