Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.06541 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929703228538880 |
|---|---|
| author | Liu, Kuikui Mani, Nitya Pernice, Francisco |
| author_facet | Liu, Kuikui Mani, Nitya Pernice, Francisco |
| contents | In a seminal paper, Weitz showed that for two-state spin systems, such as the Ising and hardcore models from statistical physics, correlation decay on trees implies correlation decay on arbitrary graphs. The key gadget in Weitz's reduction has been instrumental in recent advances in approximate counting and sampling, from analysis of local Markov chains like Glauber dynamics to the design of deterministic algorithms for estimating the partition function. A longstanding open problem in the field has been to find such a reduction for more general multispin systems like the uniform distribution over proper colorings of a graph.
In this paper, we show that for a rich class of multispin systems, including the ferromagnetic Potts model, there are fundamental obstacles to extending Weitz's reduction to the multispin setting. A central component of our investigation is establishing nonconvexity of the image of the belief propagation functional, the standard tool for analyzing spin systems on trees. On the other hand, we provide evidence of convexity for the antiferromagnetic Potts model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_06541 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Counterexamples to a Weitz-Style Reduction for Multispin Systems Liu, Kuikui Mani, Nitya Pernice, Francisco Data Structures and Algorithms Probability In a seminal paper, Weitz showed that for two-state spin systems, such as the Ising and hardcore models from statistical physics, correlation decay on trees implies correlation decay on arbitrary graphs. The key gadget in Weitz's reduction has been instrumental in recent advances in approximate counting and sampling, from analysis of local Markov chains like Glauber dynamics to the design of deterministic algorithms for estimating the partition function. A longstanding open problem in the field has been to find such a reduction for more general multispin systems like the uniform distribution over proper colorings of a graph. In this paper, we show that for a rich class of multispin systems, including the ferromagnetic Potts model, there are fundamental obstacles to extending Weitz's reduction to the multispin setting. A central component of our investigation is establishing nonconvexity of the image of the belief propagation functional, the standard tool for analyzing spin systems on trees. On the other hand, we provide evidence of convexity for the antiferromagnetic Potts model. |
| title | Counterexamples to a Weitz-Style Reduction for Multispin Systems |
| topic | Data Structures and Algorithms Probability |
| url | https://arxiv.org/abs/2411.06541 |