  We present an $\tilde O(m+n^{1.5})$-time randomized algorithm for maximum
cardinality bipartite matching and related problems (e.g. transshipment,
negative-weight shortest paths, and optimal transport) on $m$-edge, $n$-node
graphs. For maximum cardinality bipartite matching on moderately dense graphs,
i.e. $m = \Omega(n^{1.5})$, our algorithm runs in time nearly linear in the
input size and constitutes the first improvement over the classic
$O(m\sqrt{n})$-time [Dinic 1970; Hopcroft-Karp 1971; Karzanov 1973] and $\tilde
O(n^\omega)$-time algorithms [Ibarra-Moran 1981; Mucha-Sankowski 2004] (where
currently $\omega\approx 2.373$). On sparser graphs, i.e. when $m = n^{9/8 +
\delta}$ for any constant $\delta>0$, our result improves upon the recent
advances of [Madry 2013] and [Liu-Sidford 2020b, 2020a] which achieve an
$\tilde O(m^{4/3+o(1)})$ runtime.
  We obtain these results by combining and advancing recent lines of research
in interior point methods (IPMs) and dynamic graph algorithms. First, we
simplify and improve the IPM of [v.d.Brand-Lee-Sidford-Song 2020], providing a
general primal-dual IPM framework and new sampling-based techniques for
handling infeasibility induced by approximate linear system solvers. Second, we
provide a simple sublinear-time algorithm for detecting and sampling
high-energy edges in electric flows on expanders and show that when combined
with recent advances in dynamic expander decompositions, this yields efficient
data structures for maintaining the iterates of both [v.d.Brand et al.] and our
new IPMs. Combining this general machinery yields a simpler $\tilde O(n
\sqrt{m})$ time algorithm for matching based on the logarithmic barrier
function, and our state-of-the-art $\tilde O(m+n^{1.5})$ time algorithm for
matching based on the [Lee-Sidford 2014] barrier (as regularized in [v.d.Brand
et al.]).
