  We study the computational complexity of approximately counting the number of
independent sets of a graph with maximum degree Delta. More generally, for an
input graph G=(V,E) and an activity lambda>0, we are interested in the quantity
Z_G(lambda) defined as the sum over independent sets I weighted as w(I) =
lambda^|I|. In statistical physics, Z_G(lambda) is the partition function for
the hard-core model, which is an idealized model of a gas where the particles
have non-negibile size.
  Recently, an interesting phase transition was shown to occur for the
complexity of approximating the partition function. Weitz showed an FPAS for
the partition function for any graph of maximum degree Delta when Delta is
constant and lambda< lambda_c(Tree_Delta):=(Delta-1)^(Delta-1)/(Delta-2)^Delta.
The quantity lambda_c(Tree_Delta) is the critical point for the so-called
uniqueness threshold on the infinite, regular tree of degree Delta. On the
other side, Sly proved that there does not exist efficient (randomized)
approximation algorithms for lambda_c(Tree_Delta) < lambda <
lambda_c(Tree_Delta)+epsilon(Delta), unless NP=RP, for some function
epsilon(Delta)>0. We remove the upper bound in the assumptions of Sly's result
for Delta not equal to 4 and 5, that is, we show that there does not exist
efficient randomized approximation algorithms for all
lambda>lambda_c(Tree_Delta) for Delta=3 and Delta>= 6. Sly's inapproximability
result uses a clever reduction, combined with a second-moment analysis of
Mossel, Weitz and Wormald which prove torpid mixing of the Glauber dynamics for
sampling from the associated Gibbs distribution on almost every regular graph
of degree Delta for the same range of lambda as in Sly's result. We extend
Sly's result by improving upon the technical work of Mossel et al., via a more
detailed analysis of independent sets in random regular graphs.
