  We study the hard-core model defined on independent sets of an input graph
where the independent sets are weighted by a parameter $\lambda>0$. For
constant $\Delta$, previous work of Weitz (2006) established an FPTAS for the
partition function for graphs of maximum degree $\Delta$ when $\lambda<
\lambda_c(\Delta)$. The threshold $\lambda_c(\Delta)$ is the critical point for
the phase transition for uniqueness/non-uniqueness on the infinite
$\Delta$-regular trees. Sly (2010) showed that there is no FPRAS, unless NP=RP,
when $\lambda>\lambda_c(\Delta)$. The running time of Weitz's algorithm is
exponential in $\log(\Delta)$. Here we present an FPRAS for the partition
function whose running time is $O^*(n^2)$. We analyze the simple single-site
Glauber dynamics for sampling from the associated Gibbs distribution. We prove
there exists a constant $\Delta_0$ such that for all graphs with maximum degree
$\Delta\geq\Delta_0$ and girth $\geq 7$, the mixing time of the Glauber
dynamics is $O(n\log(n))$ when $\lambda<\lambda_c(\Delta)$. Our work
complements that of Weitz which applies for constant $\Delta$ whereas our work
applies for all $\Delta \geq \Delta_0$.
  We utilize loopy BP (belief propagation), a widely-used inference algorithm.
A novel aspect of our work is using the principal eigenvector for the BP
operator to design a distance function which contracts in expectation for pairs
of states that behave like the BP fixed point. We also prove that the Glauber
dynamics behaves locally like loopy BP. As a byproduct we obtain that the
Glauber dynamics converges, after a short burn-in period, close to the BP fixed
point, and this implies that the fixed point of loopy BP is a close
approximation to the Gibbs distribution. Using these connections we establish
that loopy BP quickly converges to the Gibbs distribution when the girth $\geq
6$ and $\lambda<\lambda_c(\Delta)$.
