  We consider local Markov chain Monte-Carlo algorithms for sampling from the
weighted distribution of independent sets with activity $\l$, where the weight
of an independent set $I$ is $\l^{|I|}$. A recent result has established that
Gibbs sampling is rapidly mixing in sampling the distribution for graphs of
maximum degree $d$ and $\l<\l_c(d)$, where $\l_c(d)$ is the critical activity
for uniqueness of the Gibbs measure (i.e., for decay of correlations with
distance in the weighted distribution over independent sets) on the $d$-regular
infinite tree.
  We show that for $d \geq 3$, $\l$ just above $\l_c(d)$ with high probability
over $d$-regular bipartite graphs, any local Markov chain Monte-Carlo algorithm
takes exponential time before getting close to the stationary distribution.
  Our results provide a rigorous justification for ``replica'' method
heuristics. These heuristics were invented in theoretical physics and are used
in order to derive predictions on Gibbs measures on random graphs in terms of
Gibbs measures on trees. We conjecture that $\l_c$ is in fact the exact
threshold for this computational problem, i.e., that for $\l>\l_c$ it is
NP-hard to approximate the above weighted sum overindependent sets to within a
factor polynomial in the size of the graph.
