  We investigate the time-complexity of the All-Pairs Max-Flow problem: Given a
graph with $n$ nodes and $m$ edges, compute for all pairs of nodes the
maximum-flow value between them. If Max-Flow (the version with a given
source-sink pair $s,t$) can be solved in time $T(m)$, then an $O(n^2) \cdot
T(m)$ is a trivial upper bound. But can we do better?
  For directed graphs, recent results in fine-grained complexity suggest that
this time bound is essentially optimal. In contrast, for undirected graphs with
edge capacities, a seminal algorithm of Gomory and Hu (1961) runs in much
faster time $O(n)\cdot T(m)$. Under the plausible assumption that Max-Flow can
be solved in near-linear time $m^{1+o(1)}$, this half-century old algorithm
yields an $nm^{1+o(1)}$ bound. Several other algorithms have been designed
through the years, including $\tilde{O}(mn)$ time for unit-capacity edges
(unconditionally), but none of them break the $O(mn)$ barrier. Meanwhile, no
super-linear lower bound was shown for undirected graphs.
  We design the first hardness reductions for All-Pairs Max-Flow in undirected
graphs, giving an essentially optimal lower bound for the
$\textit{node-capacities}$ setting. For edge capacities, our efforts to prove
similar lower bounds have failed, but we have discovered a surprising new
algorithm that breaks the $O(mn)$ barrier for graphs with unit-capacity edges!
Assuming $T(m)=m^{1+o(1)}$, our algorithm runs in time $m^{3/2 +o(1)}$ and
outputs a cut-equivalent tree (similarly to the Gomory-Hu algorithm). Even with
current Max-Flow algorithms we improve state-of-the-art as long as
$m=O(n^{5/3-\varepsilon})$. Finally, we explain the lack of lower bounds by
proving a $\textit{non-reducibility}$ result. This result is based on a new
quasi-linear time $\tilde{O}(m)$ $\textit{non-deterministic}$ algorithm for
constructing a cut-equivalent tree and may be of independent interest.
