Approximate Counting via Correlation Decay in Spin Systems

Details Approximate Counting via Correlation Decay in Spin Systems Approximate Counting via Correlation Decay in Spin Systems

2011-09-03

arxiv.org/abs/1109.0604v2

Computer Science

Data Structures and Algorithms

29 pages, 1 figure, to appear in SODA 2012

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Approximate Counting via Correlation Decay in Spin Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximate Counting via Correlation Decay in Spin Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Counting via Correlation Decay in Spin Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-147956