DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2024.45

Two-State Spin Systems with Negative Interactions

Authors: Yumou Fei, Leslie Ann Goldberg, and Pinyan Lu

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

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.

Cite as

Yumou Fei, Leslie Ann Goldberg, and Pinyan Lu. Two-State Spin Systems with Negative Interactions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 45:1-45:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fei_et_al:LIPIcs.ITCS.2024.45,
  author =	{Fei, Yumou and Goldberg, Leslie Ann and Lu, Pinyan},
  title =	{{Two-State Spin Systems with Negative Interactions}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{45:1--45:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.45},
  URN =		{urn:nbn:de:0030-drops-195739},
  doi =		{10.4230/LIPIcs.ITCS.2024.45},
  annote =	{Keywords: Approximate Counting, Spin Systems, #P-Hardness, Randomized Algorithms}
}

Search Results

Documents authored by Fei, Yumou

Two-State Spin Systems with Negative Interactions

Abstract

Cite as

Thanks for your feedback!

Could not send message