Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12704
- Type
- D - Journal article
- DOI
-
10.1137/17M1127144
- Title of journal
- SIAM Journal on Computing
- Article number
- -
- First page
- 581
- Volume
- 48
- Issue
- 2
- ISSN
- 0097-5397
- Open access status
- Deposit exception
- Month of publication
- April
- Year of publication
- 2019
- 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
-
4
- Research group(s)
-
T - Theory and Foundations
- Citation count
- 1
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This well-cited research was selected for the journal special issue for one of the top two theory conferences FOCS 2016. It is on a fundamental problem also studied in physics and mathematics, and worked on by renowned researchers including Dyer (Fulkerson Prize 1991) and Sinclair (Fulkerson Prize 2006). The proposed Monte Carlo algorithm is for a parameter region that complements the hardness region shown by Sly (Princeton) in a celebrated result that relates phase transitions and computational hardness. This research also reveals novel connections between Monte Carlo algorithms and the loopy Belief Propagation algorithm of Pearl (Turing Award 2011).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -