Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
- Submitting institution
-
University of Oxford
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 1973
- Type
- D - Journal article
- DOI
-
-
- Title of journal
- JOURNAL OF THE ACM
- Article number
- ARTN 50
- First page
- 1
- Volume
- 62
- Issue
- 6
- ISSN
- 0004-5411
- Open access status
- Out of scope for open access requirements
- Month of publication
- December
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
https://dl.acm.org/doi/10.1145/2785964#sec-supp
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
-
- Citation count
- 17
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This JACM paper had a conference version in STOC 2014. The paper gives strong inapproximability results for a general class of counting problems, including the well-studied k-colouring and Potts models. The main novelty of the paper was to introduce tools from the theory of induced matrix norms to analyse general spin models on bipartite regular graphs. For the colouring and Potts models in particular, the inapproximability results of the paper were a surprising leap from the current state of the art, confirming a conjecture that the uniqueness phase transition on the tree also marks a computational hardness transition.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -