  We present a deterministic approximation algorithm to compute logarithm of
the number of `good' truth assignments for a random k-satisfiability (k-SAT)
formula in polynomial time (by `good' we mean that violate a small fraction of
clauses). The relative error is bounded above by an arbitrarily small constant
epsilon with high probability as long as the clause density (ratio of clauses
to variables) alpha<alpha_{u}(k) = 2k^{-1}\log k(1+o(1)). The algorithm is
based on computation of marginal distribution via belief propagation and use of
an interpolation procedure. This scheme substitutes the traditional one based
on approximation of marginal probabilities via MCMC, in conjunction with
self-reduction, which is not easy to extend to the present problem.
  We derive 2k^{-1}\log k (1+o(1)) as threshold for uniqueness of the Gibbs
distribution on satisfying assignment of random infinite tree k-SAT formulae to
establish our results, which is of interest in its own right.
