Journal article
Two-state spin systems with negative interactions
- Abstract:
- We study the approximability of computing the partition functions of two-state spin systems. The problem is parameterized by a 2 × 2 symmetric matrix. Previous results on this problem were restricted either to the case where the matrix has non-negative entries, or to the case where the diagonal entries are equal, i.e. Ising models. In this paper, we study the generalization to arbitrary 2 × 2 interaction matrices with real entries. We show that in some regions of the parameter space, it’s #P-hard to even determine the sign of the partition function, while in other regions there are fully polynomial approximation schemes for the partition function. Our results reveal several new computational phase transitions.
- Publication status:
- In press
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 565.8KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.ic.2025.105340
Authors
- Publisher:
- Elsevier
- Journal:
- Information and Computation More from this journal
- Publication date:
- 2025-08-25
- Acceptance date:
- 2025-08-14
- DOI:
- EISSN:
-
1090-2651
- ISSN:
-
0890-5401
- Language:
-
English
- Pubs id:
-
2281457
- Local pid:
-
pubs:2281457
- Deposit date:
-
2025-08-15
Terms of use
- Copyright holder:
- Elsevier Inc.
- Copyright date:
- 2025
- Rights statement:
- © 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
- Notes:
- For the purpose of Open Access, the authors have applied a CC BY public copyright licence to any Author Accepted Manuscript version arising from this submission. All data is provided in full in the results section of this paper.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record