  Maximum bipartite matching (MBM) is a fundamental problem in combinatorial
optimization with a long and rich history. A classic result of Hopcroft and
Karp (1973) provides an $O(m \sqrt{n})$-time algorithm for the problem, where
$n$ and $m$ are the number of vertices and edges in the input graph,
respectively. For dense graphs, an approach based on fast matrix multiplication
achieves a running time of $O(n^{2.371})$. For several decades, these results
represented state-of-the-art algorithms, until, in 2013, Madry introduced a
powerful new approach for solving MBM using continuous optimization techniques.
This line of research led to several spectacular results, culminating in a
breakthrough $m^{1+o(1)}$-time algorithm for min-cost flow, that implies an
$m^{1+o(1)}$-time algorithm for MBM as well.
  These striking advances naturally raise the question of whether combinatorial
algorithms can match the performance of the algorithms that are based on
continuous techniques for MBM. A recent work of the authors (2024) made
progress on this question by giving a combinatorial
$\tilde{O}(m^{1/3}n^{5/3})$-time algorithm for MBM, thus outperforming both the
Hopcroft-Karp algorithm and matrix multiplication based approaches, on
sufficiently dense graphs. Still, a large gap remains between the running time
of their algorithm and the almost linear-time achievable by algorithms based on
continuous techniques. In this work, we take another step towards narrowing
this gap, and present a randomized $n^{2+o(1)}$-time combinatorial algorithm
for MBM. Thus in dense graphs, our algorithm essentially matches the
performance of algorithms that are based on continuous methods. We also obtain
a randomized $n^{2+o(1)}$-time combinatorial algorithm for maximum
vertex-capacitated $s$-$t$ flow in directed graphs when all vertex capacities
are identical, using a standard reduction from this problem to MBM.
