{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T19:05:36Z","timestamp":1777489536794,"version":"3.51.4"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T00:00:00Z","timestamp":1555027200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1420934"],"award-info":[{"award-number":["CCF-1420934"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Google research fellowship at the Simons Institute"},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/N004221\/1"],"award-info":[{"award-number":["EP\/N004221\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>\n            We propose a new algorithmic framework, called\n            <jats:italic>partial rejection sampling<\/jats:italic>\n            , to draw samples exactly from a product distribution, conditioned on none of a number of bad events occurring. Our framework builds new connections between the variable framework of the Lov\u00e1sz Local Lemma and some classical sampling algorithms such as the cycle-popping algorithm for rooted spanning trees. Among other applications, we discover new algorithms to sample satisfying assignments of\n            <jats:italic>k<\/jats:italic>\n            -CNF formulas with bounded variable occurrences.\n          <\/jats:p>","DOI":"10.1145\/3310131","type":"journal-article","created":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T12:07:04Z","timestamp":1555330024000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Uniform Sampling Through the Lov\u00e1sz Local Lemma"],"prefix":"10.1145","volume":"66","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8199-5596","authenticated-orcid":false,"given":"Heng","family":"Guo","sequence":"first","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[{"name":"Queen Mary, University of London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingcheng","family":"Liu","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818352"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020403"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"e_1_2_1_4_1","first-page":"1","article-title":"Approximation via correlation decay when strong spatial mixing fails","volume":"45","author":"Bez\u00e1kov\u00e1 Ivona","year":"2016","unstructured":"Ivona Bez\u00e1kov\u00e1 , Andreas Galanis , Leslie Ann Goldberg , Heng Guo , and Daniel \u0160tefankovi\u010d . 2016 . Approximation via correlation decay when strong spatial mixing fails . In Proceedings of ICALP. 45 : 1 -- 13 . Ivona Bez\u00e1kov\u00e1, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel \u0160tefankovi\u010d. 2016. Approximation via correlation decay when strong spatial mixing fails. In Proceedings of ICALP. 45:1--13.","journal-title":"Proceedings of ICALP."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_11"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/314161.314263"},{"key":"e_1_2_1_7_1","article-title":"Generating a random sink-free orientation in quadratic time","volume":"9","author":"Cohn Henry","year":"2002","unstructured":"Henry Cohn , Robin Pemantle , and James G. Propp . 2002 . Generating a random sink-free orientation in quadratic time . Electr. J. Comb. 9 , 1 (2002), 13 pages. Research Paper 10. Henry Cohn, Robin Pemantle, and James G. Propp. 2002. Generating a random sink-free orientation in quadratic time. Electr. J. Comb. 9, 1 (2002), 13 pages. Research Paper 10.","journal-title":"Electr. J. Comb."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/360708.360729"},{"key":"e_1_2_1_9_1","series-title":"Colloquia Mathematica Societatis J\u00e1nos Bolyai","volume-title":"Infinite and Finite Sets","author":"Erd\u0151s Paul","unstructured":"Paul Erd\u0151s and L\u00e1szl\u00f3 Lov\u00e1sz . 1975. Problems and results on 3-chromatic hypergraphs and some related questions . In Infinite and Finite Sets , Volume 10 of Colloquia Mathematica Societatis J\u00e1nos Bolyai . North Holland , 609--628. Paul Erd\u0151s and L\u00e1szl\u00f3 Lov\u00e1sz. 1975. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets, Volume 10 of Colloquia Mathematica Societatis J\u00e1nos Bolyai. North Holland, 609--628."},{"key":"e_1_2_1_10_1","unstructured":"Weiming Feng Yahui Liu and Yitong Yin. 2018. Local rejection sampling with soft filters. arXiv:1807.06481.  Weiming Feng Yahui Liu and Yitong Yin. 2018. Local rejection sampling with soft filters. arXiv:1807.06481."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087815"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000401"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2975386"},{"key":"e_1_2_1_14_1","unstructured":"Heng Guo and Kun He. 2018. Tight bounds for popping algorithms. arXiv:1807.01680.  Heng Guo and Kun He. 2018. Tight bounds for popping algorithms. arXiv:1807.01680."},{"key":"e_1_2_1_15_1","unstructured":"Heng Guo and Mark Jerrum. 2018. Approximately counting bases of bicircular matroids. arXiv:1808.09548.  Heng Guo and Mark Jerrum. 2018. Approximately counting bases of bicircular matroids. arXiv:1808.09548."},{"key":"e_1_2_1_16_1","volume-title":"ICALP (LIPIcs)","volume":"107","author":"Guo Heng","year":"2018","unstructured":"Heng Guo and Mark Jerrum . 2018 . Perfect simulation of the hard disks model by partial rejection sampling . In ICALP (LIPIcs) , Vol. 107 . Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 69:1--69:10. Heng Guo and Mark Jerrum. 2018. Perfect simulation of the hard disks model by partial rejection sampling. In ICALP (LIPIcs), Vol. 107. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 69:1--69:10."},{"key":"e_1_2_1_17_1","volume-title":"ICALP (LIPIcs)","volume":"107","author":"Guo Heng","year":"2018","unstructured":"Heng Guo and Mark Jerrum . 2018 . A polynomial-time approximation algorithm for all-terminal network reliability . In ICALP (LIPIcs) , Vol. 107 . Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 68:1--68:12. Heng Guo and Mark Jerrum. 2018. A polynomial-time approximation algorithm for all-terminal network reliability. In ICALP (LIPIcs), Vol. 107. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 68:1--68:12."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055410"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049702"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488696"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.57"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634142"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.85"},{"key":"e_1_2_1_24_1","unstructured":"Jonathan Hermon Allan Sly and Yumeng Zhang. 2016. Rapid mixing of hypergraph independent set. arXiv:1610.07999.  Jonathan Hermon Allan Sly and Yumeng Zhang. 2016. Rapid mixing of hypergraph independent set. arXiv:1610.07999."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2898950"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993669"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722230"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Ankur Moitra. 2016. Approximate counting the Lov\u00e1sz local lemma and inference in graphical models. arXiv:1610.04317.  Ankur Moitra. 2016. Approximate counting the Lov\u00e1sz local lemma and inference in graphical models. arXiv:1610.04317.","DOI":"10.1145\/3055399.3055428"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276866"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/235610.235641"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0917"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-004-2055-4"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579368"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOP888"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347150"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237880"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3310131","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3310131","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3310131","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:13:15Z","timestamp":1750212795000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3310131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,12]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3310131"],"URL":"https:\/\/doi.org\/10.1145\/3310131","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,12]]},"assertion":[{"value":"2017-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}