  We propose a deterministic algorithm for approximately counting the number of
list colorings of a graph. Under the assumption that the graph is triangle
free, the size of every list is at least $\alpha \Delta$, where $\alpha$ is an
arbitrary constant bigger than $\alpha^{**}=2.8432...$, and $\Delta$ is the
maximum degree of the graph, we obtain the following results. For the case when
the size of the each list is a large constant, we show the existence of a
\emph{deterministic} FPTAS for computing the total number of list colorings.
The same deterministic algorithm has complexity $2^{O(\log^2 n)}$, without any
assumptions on the sizes of the lists, where $n$ is the instance size. We
further extend our method to a discrete Markov random field (MRF) model. Under
certain assumptions relating the size of the alphabet, the degree of the graph
and the interacting potentials we again construct a deterministic FPTAS for
computing the partition function of a MRF.
  Our results are not based on the most powerful existing counting technique --
rapidly mixing Markov chain method. Rather we build upon concepts from
statistical physics, in particular, the decay of correlation phenomena and its
implication for the uniqueness of Gibbs measures in infinite graphs. This
approach was proposed in two recent papers \cite{BandyopadhyayGamarnikCounting}
and \cite{weitzCounting}. The principle insight of this approach is that the
correlation decay property can be established with respect to certain
\emph{computation tree}, as opposed to the conventional correlation decay
property with respect to graph theoretic neighborhoods of a given node. This
allows truncation of computation at a logarithmic depth in order to obtain
polynomial accuracy in polynomial time.
