#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- Submitting institution
-
University of Oxford
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 1971
- Type
- D - Journal article
- DOI
-
10.1016/j.jcss.2015.11.009
- Title of journal
- Journal of Computer and Systems Sciences International
- Article number
- -
- First page
- 690
- Volume
- 82
- Issue
- 5
- ISSN
- 1064-2307
- Open access status
- Out of scope for open access requirements
- Month of publication
- January
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
-
- 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
-
6
- Research group(s)
-
-
- Citation count
- 14
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper gives tight inapproximability results for antiferromagnetic 2-spin counting problems on bipartite graphs, such as counting independent sets or estimating the partition function of the Ising model. These results complemented earlier algorithmic results of Sinclair, Srivastava, and Thurley (SODA 2012) and Li, Lu, and Yin (SODA 2013), and thus fully resolved the complexity picture on bipartite graphs. This paper has subsequently been used as a starting point to study the complexity of related approximate counting problems (e.g., see Liu, Lu, and Zhang APPROX/RANDOM 2014 https://drops.dagstuhl.de/opus/volltexte/2014/4742/).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -