Abstract / Description of output
For anti-ferromagnetic 2-spin systems, a beautiful connection has been established, namely
that the following three notions align perfectly: the uniqueness of Gibbs measures in infinite
regular trees, the decay of correlations (also known as spatial mixing), and the approximability
of the partition function. The uniqueness condition implies spatial mixing, and an FPTAS for the
partition function exists based on spatial mixing. On the other hand, non-uniqueness implies
some long range correlation, based on which NP-hardness reductions are built.
These connections for ferromagnetic 2-spin systems are much less clear, despite their similarities
to anti-ferromagnetic systems. The celebrated Jerrum-Sinclair Markov chain [JS93] works
even if spatial mixing fails. Also, for a fixed degree the uniqueness condition is non-monotone
with respect to the external field, which seems to have no meaningful interpretation in terms
of computational complexity. However, it is still intriguing whether there are some relationship
underneath the apparent disparities among them.
We provide some answers to this question. Let ;
be the (0; 0) and (1; 1) edge interactions
respectively (
> 1), and the external field for spin “0”. For graphs with degree bound
Δ Δc + 1 where Δc =
p
p
+1
-1
, regardless of the field (even inconsistent fields are allowed),
correlation decay always holds and FPTAS exists. If all fields satisfy < c (assuming
),
where c = (
=)
Δc+1
2 , then a weaker version of spatial mixing holds in all trees. Moreover, if
1, then < c is sufficient to guarantee strong spatial mixing and FPTAS. This improves
the best previous algorithm, a Markov chain based FPRAS for
= [LLZ14].
The bound c is almost optimal and can be viewed as a variant of the uniqueness condition
with the degree d relaxed to be a real number instead of an integer. When 1, uniqueness
holds in all infinite regular trees, if and only if int
c , where int
c = (
=)
⌈Δc⌉+1
2 . If we
allow fields > int
c
′, where int
c
′
= (
=)
⌊Δc⌋+2
2 , then approximating the partition function is
#BIS-hard.
Interestingly, unless Δc is an integer, neither c nor int
c is the tight bound in each own
respect. We provide examples where correlation decay continues to hold in a small interval
beyond c, and irregular trees in which spatial mixing fails for some < int
c .
Original language | English |
---|---|
Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France |
Place of Publication | Paris, France |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pages | 31:1-31:26 |
Number of pages | 26 |
Volume | 60 |
ISBN (Electronic) | 978-3-95977-018-7 |
DOIs | |
Publication status | E-pub ahead of print - 9 Sept 2016 |
Event | 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems / 20th International Workshop on Randomization and Computation - Paris, France Duration: 7 Sept 2016 → 9 Sept 2016 http://cui.unige.ch/tcs/random-approx/2016/ |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Publisher | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik |
Volume | 60 |
ISSN (Electronic) | 1868-8969 |
Conference
Conference | 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems / 20th International Workshop on Randomization and Computation |
---|---|
Abbreviated title | APPROX / RANDOM 2016 |
Country/Territory | France |
City | Paris |
Period | 7/09/16 → 9/09/16 |
Internet address |