FERROMAGNETIC POTTS MODEL: REFINED #BIS-HARDNESS AND RELATED RESULTS
- Submitting institution
-
University of Oxford
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 2007
- Type
- D - Journal article
- DOI
-
-
- Title of journal
- SIAM JOURNAL ON COMPUTING
- Article number
- -
- First page
- 2004
- Volume
- 45
- Issue
- 6
- ISSN
- 0097-5397
- Open access status
- Compliant
- Month of publication
- November
- Year of publication
- 2016
- 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
-
3
- Research group(s)
-
-
- Citation count
- 12
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This SICOMP paper extends a conference version in APPROX/RANDOM 2014. The paper studies the complexity of approximately sampling from the ferromagnetic Potts model, and gives an extremely detailed picture extending an important inapproximability result of Goldberg and Jerrum (Journal of the ACM, 2012). The paper accomplishes this by giving a meticulous analysis of the phase transitions of the model on regular graphs. The thresholds established in this paper have also been used as a benchmark to study the effectiveness of approximate sampling algorithms on expander graphs (see, e.g., Jensseen, Keevash, and Perkins SODA 2018 and related follow-up work).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -