  In this paper we study the classic problem of computing a maximum cardinality
matching in general graphs $G = (V, E)$. The best known algorithm for this
problem till date runs in $O(m \sqrt{n})$ time due to Micali and Vazirani
\cite{MV80}. Even for general bipartite graphs this is the best known running
time (the algorithm of Karp and Hopcroft \cite{HK73} also achieves this bound).
For regular bipartite graphs one can achieve an $O(m)$ time algorithm which,
following a series of papers, has been recently improved to $O(n \log n)$ by
Goel, Kapralov and Khanna (STOC 2010) \cite{GKK10}. In this paper we present a
randomized algorithm based on the Markov Chain Monte Carlo paradigm which runs
in $O(m \log^2 n)$ time, thereby obtaining a significant improvement over
\cite{MV80}.
  We use a Markov chain similar to the \emph{hard-core model} for Glauber
Dynamics with \emph{fugacity} parameter $\lambda$, which is used to sample
independent sets in a graph from the Gibbs Distribution \cite{V99}, to design a
faster algorithm for finding maximum matchings in general graphs. Our result
crucially relies on the fact that the mixing time of our Markov Chain is
independent of $\lambda$, a significant deviation from the recent series of
works \cite{GGSVY11,MWW09, RSVVY10, S10, W06} which achieve computational
transition (for estimating the partition function) on a threshold value of
$\lambda$. As a result we are able to design a randomized algorithm which runs
in $O(m\log^2 n)$ time that provides a major improvement over the running time
of the algorithm due to Micali and Vazirani. Using the conductance bound, we
also prove that mixing takes $\Omega(\frac{m}{k})$ time where $k$ is the size
of the maximum matching.
