We present randomized algorithms for finding maximum matchings in general and bipartite graphs. Both algorithms have running time O(n^\omega), where \omega is the exponent of the best known matrix multiplication algorithm. Since \omega < 2.38, these algorithms break through the O(n^{2.5} ) barrier for the matching problem. They both have a very simple implementation in time O(n³) and the only non-trivial element of the O(n^\omega) bipartite matching algorithm is the fast matrix multiplication algorithm.

Our results resolve a long-standing open question of whether Lovász's randomized technique of testing graphs for perfect matching in time O(n^\omega) can be extended to an algorithm that actually constructs a perfect matching.