NDLI: Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region

Content Provider	ACM Digital Library
Author	Galanis, Andreas tefankovi, Daniel Vigoda, Eric
Copyright Year	2015
Abstract	A remarkable connection has been established for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree Δ undergoes a phase transition that coincides with the statistical physics uniqueness/nonuniqueness phase transition on the infinite Δ-regular tree. Despite this clear picture for 2-spin systems, there is little known for multispin systems. We present the first analog of this in approximability results for multispin systems. The main difficulty in previous inapproximability results was analyzing the behavior of the model on random Δ-regular bipartite graphs, which served as the gadget in the reduction. To this end, one needs to understand the moments of the partition function. Our key contribution is connecting: (i) induced matrix norms, (ii) maxima of the expectation of the partition function, and (iii) attractive fixed points of the associated tree recursions (belief propagation). The view through matrix norms allows a simple and generic analysis of the second moment for any spin system on random Δ-regular bipartite graphs. This yields concentration results for any spin system in which one can analyze the maxima of the first moment. The connection to fixed points of the tree recursions enables an analysis of the maxima of the first moment for specific models of interest. For $\textit{k}-colorings$ we prove that for even $\textit{k},$ in a tree nonuniqueness region (which corresponds to $\textit{k}$ < Δ) there is no FPRAS, unless NP = RP, to approximate the number of colorings for triangle-free Δ-regular graphs. Our proof extends to the antiferromagnetic Potts model, and, in fact, to every antiferromagnetic model under a mild condition.
Starting Page	1
Ending Page	60
Page Count	60
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2785964
Journal	Journal of the ACM (JACM)
Volume Number	62
Issue Number	6
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-12-10
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Approximate counting Inapproximability Phase transitions Random regular graphs
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region

On counting homomorphisms to directed acyclic graphs

Eigenvalues and expansion of regular graphs

Counting is easy

Permutation Graphs and Transitive Graphs

Transitions 1959--1964

Addressable Data Graphs

On sufficient conditions for unsatisfiability of random formulas

The HOM problem is decidable

Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region

Similar Documents

Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region

On counting homomorphisms to directed acyclic graphs

Eigenvalues and expansion of regular graphs

Counting is easy

Permutation Graphs and Transitive Graphs

Transitions 1959--1964

Addressable Data Graphs

On sufficient conditions for unsatisfiability of random formulas

The HOM problem is decidable

Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region