  We give the first deterministic fully polynomial-time approximation scheme
(FPTAS) for computing the partition function of a two-state spin system on an
arbitrary graph, when the parameters of the system satisfy the uniqueness
condition on infinite regular trees. This condition is of physical significance
and is believed to be the right boundary between approximable and
inapproximable.
  The FPTAS is based on the correlation decay technique introduced by
Bandyopadhyay and Gamarnik [SODA 06] and Weitz [STOC 06]. The classic
correlation decay is defined with respect to graph distance. Although this
definition has natural physical meanings, it does not directly support an FPTAS
for systems on arbitrary graphs, because for graphs with unbounded degrees, the
local computation that provides a desirable precision by correlation decay may
take super-polynomial time. We introduce a notion of computationally efficient
correlation decay, in which the correlation decay is measured in a refined
metric instead of graph distance. We use a potential method to analyze the
amortized behavior of this correlation decay and establish a correlation decay
that guarantees an inverse-polynomial precision by polynomial-time local
computation. This gives us an FPTAS for spin systems on arbitrary graphs. This
new notion of correlation decay properly reflects the algorithmic aspect of the
spin systems, and may be used for designing FPTAS for other counting problems.
