This stunning result is in an area that is outside my expertise, but I can appreciate it nevertheless. The issue is the relative hardness of all-pairs max-flow (APMF) versus all-pairs shortest paths (APSP) in general undirected graphs with general (binary) weights. The main result is that APMF can be solved in strictly sub-cubic time; the original posting (of Nov 9th) claimed a time bound of $\tildeO(n^{23/8})$, whereas version 2 (of Nov 30th) claims an almost quadratic bound, which is essentially optimal.
This result disproves prior beliefs by which APMF is harder than APSP. Recall that it is widely conjectured that APSP requires almost cubic time. So if this conjecture (or even milder forms of it) is true, then APMF is significantly easier than APSP, and otherwise both problems have approximately the same complexity.
In 1961, Gomory and Hu showed that the max-flow values of all ($n\choose2$) pairs of vertices in an undirected graph can be computed using only $n-1$ calls to any max-flow algorithm, and succinctly represented them in a tree (called the Gomory-Hu tree later). Even assuming a linear-time max-flow algorithm, this yields a running time of $O(mn)$ for this problem; with current max-flow algorithms, the running time is $\tildeO(mn+n^{5/2})$. We break this 60-year old barrier by giving an $\tildeO(n^2)$-time algorithm for the Gomory-Hu tree problem, already with current max-flow algorithms. For unweighted graphs, our techniques show equivalence (up to poly-logarithmic factors in running time) between Gomory-Hu tree (i.e., all-pairs max-flow values) and a single-pair max-flow.
Available from arXiv:2111.04958 [cs.DS].