@article{d42825e064384b50abfeb96659172e12,
title = "Perfect sampling from spatial mixing",
abstract = "We introduce a new perfect sampling technique that can be applied to general Gibbs distributions and runs in linear time if the correlation decays faster than the neighborhood growth. In particular, in graphs with sub-exponential neighborhood growth like Z푑, our algorithm achieves linear running time as long as Gibbs sampling is rapidly mixing. As concrete applications, we obtain the currently best perfect samplers for colorings and for monomer-dimer models in such graphs.",
keywords = "perfect sampling, Gibbs distribution, spatial mixing",
author = "Weiming Feng and Heng Guo and Yitong Yin",
note = "Funding Information: information European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, 947778We thank Jingcheng Liu for helpful comments. Heng Guo and Yitong Yin want to thank the hospitality of the Simons Institute for the Theory of Computing at UC Berkeley, where part of the work was done. This research has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 947778). Funding Information: European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, 947778 Funding information Funding Information: We thank Jingcheng Liu for helpful comments. Heng Guo and Yitong Yin want to thank the hospitality of the Simons Institute for the Theory of Computing at UC Berkeley, where part of the work was done. This research has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 947778). Publisher Copyright: {\textcopyright} 2022 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC.",
year = "2022",
month = dec,
day = "1",
doi = "10.1002/rsa.21079",
language = "English",
volume = "61",
pages = "678--709",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "John Wiley & Sons Inc.",
number = "4",
}