{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,14]],"date-time":"2026-11-14T09:42:37Z","timestamp":1794649357816,"version":"4.9.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T00:00:00Z","timestamp":1633392000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2018YFB1003202"],"award-info":[{"award-number":["2018YFB1003202"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61902241"],"award-info":[{"award-number":["61902241"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council","award":["947778"],"award-info":[{"award-number":["947778"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            We give new algorithms based on Markov chains to sample and approximately count satisfying assignments to\n            <jats:italic>k<\/jats:italic>\n            -uniform CNF formulas where each variable appears at most\n            <jats:italic>d<\/jats:italic>\n            times. For any\n            <jats:italic>k<\/jats:italic>\n            and\n            <jats:italic>d<\/jats:italic>\n            satisfying\n            <jats:italic>kd<\/jats:italic>\n            &lt; n\n            <jats:sup>o(1)<\/jats:sup>\n            and\n            <jats:italic>k<\/jats:italic>\n            \u2265 20 log\n            <jats:italic>k<\/jats:italic>\n            + 20 log\n            <jats:italic>d<\/jats:italic>\n            + 60, the new sampling algorithm runs in close to linear time, and the counting algorithm runs in close to quadratic time.\n          <\/jats:p>\n          <jats:p>\n            Our approach is inspired by Moitra (JACM, 2019), which remarkably utilizes the Lov\u00e1sz local lemma in approximate counting. Our main technical contribution is to use the local lemma to bypass the connectivity barrier in traditional Markov chain approaches, which makes the well-developed MCMC method applicable on disconnected state spaces such as SAT solutions. The benefit of our approach is to avoid the enumeration of local structures and obtain fixed polynomial running times, even if\n            <jats:italic>k<\/jats:italic>\n            = \u03c9 (1) or  d = \u03c9 (1).\n          <\/jats:p>","DOI":"10.1145\/3469832","type":"journal-article","created":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T20:01:15Z","timestamp":1633464075000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Fast Sampling and Counting\n            <i>k<\/i>\n            -SAT Solutions in the Local Lemma Regime"],"prefix":"10.1145","volume":"68","author":[{"given":"Weiming","family":"Feng","sequence":"first","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Heng","family":"Guo","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9204-7794","authenticated-orcid":false,"given":"Yitong","family":"Yin","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chihao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1083906"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/050644033"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2414676.2414682"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646111"},{"key":"e_1_2_1_5_1","first-page":"1","article-title":"Fast algorithms at low temperatures via markov chains. In Proceedings of APPROX-RANDOM(LIPIcs, Vol. 145)","volume":"41","author":"Chen Zongchen","year":"2019","unstructured":"Zongchen Chen , Andreas Galanis , Leslie Ann Goldberg , Will Perkins , James Stewart , and Eric Vigoda . 2019 . Fast algorithms at low temperatures via markov chains. In Proceedings of APPROX-RANDOM(LIPIcs, Vol. 145) . Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik , 41 : 1 \u2013 41 :14. Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, and Eric Vigoda. 2019. Fast algorithms at low temperatures via markov chains. In Proceedings of APPROX-RANDOM(LIPIcs, Vol. 145). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 41:1\u201341:14.","journal-title":"Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1127144"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Weiming Feng Kun He and Yitong Yin. 2020. Sampling constraint satisfaction solutions in the local lemma regime. Retrieved from https:\/\/arXiv:2011.03915.   Weiming Feng Kun He and Yitong Yin. 2020. Sampling constraint satisfaction solutions in the local lemma regime. Retrieved from https:\/\/arXiv:2011.03915.","DOI":"10.1145\/3406325.3451101"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.06.005"},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"Counting solutions to random CNF formulas. In Proceedings of ICALP(LIPIcs, Vol. 168)","volume":"53","author":"Galanis Andreas","year":"2020","unstructured":"Andreas Galanis , Leslie Ann Goldberg , Heng Guo , and Kuan Yang . 2020 . Counting solutions to random CNF formulas. In Proceedings of ICALP(LIPIcs, Vol. 168) . Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik , 53 : 1 \u2013 53 :14. Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Kuan Yang. 2020. Counting solutions to random CNF formulas. In Proceedings of ICALP(LIPIcs, Vol. 168). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 53:1\u201353:14.","journal-title":"Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AAP1335"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3310131"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1202955"},{"key":"e_1_2_1_14_1","volume-title":"Harris","author":"Haeupler Bernhard","year":"2017","unstructured":"Bernhard Haeupler and David G . Harris . 2017 . Parallel algorithms and concentration bounds for the Lov\u00e1sz Local Lemma via witness-DAGs. In Proceedings of SODA. SIAM , 1170\u20131187. Bernhard Haeupler and David G. Harris. 2017. Parallel algorithms and concentration bounds for the Lov\u00e1sz Local Lemma via witness-DAGs. In Proceedings of SODA. SIAM, 1170\u20131187."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049702"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316305"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20830"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AAP1015"},{"key":"e_1_2_1_19_1","volume-title":"Huy Tuan Pham, and Thuy Duong Vuong","author":"Jain Vishesh","year":"2020","unstructured":"Vishesh Jain , Huy Tuan Pham, and Thuy Duong Vuong . 2020 . Towards the sampling Lov\u00e1sz Local Lemma. Retrieved from https:\/\/arXiv:2011.12196. Vishesh Jain, Huy Tuan Pham, and Thuy Duong Vuong. 2020. Towards the sampling Lov\u00e1sz Local Lemma. Retrieved from https:\/\/arXiv:2011.12196."},{"key":"e_1_2_1_20_1","volume-title":"Huy Tuan Pham, and Thuy-Duong Vuong","author":"Jain Vishesh","year":"2021","unstructured":"Vishesh Jain , Huy Tuan Pham, and Thuy-Duong Vuong . 2021 . On the sampling lov\u00e1sz local lemma for atomic constraint satisfaction problems. Retrieved from https:\/\/arXiv:2102.08342. Vishesh Jain, Huy Tuan Pham, and Thuy-Duong Vuong. 2021. On the sampling lov\u00e1sz local lemma for atomic constraint satisfaction problems. Retrieved from https:\/\/arXiv:2102.08342."},{"key":"e_1_2_1_21_1","volume-title":"Algorithms for #BIS-hard problems on expander graphs","author":"Jenssen Matthew","unstructured":"Matthew Jenssen , Peter Keevash , and Will Perkins . 2019. Algorithms for #BIS-hard problems on expander graphs . In Proceedings of SODA. SIAM , 2235\u20132247. Matthew Jenssen, Peter Keevash, and Will Perkins. 2019. Algorithms for #BIS-hard problems on expander graphs. In Proceedings of SODA. SIAM, 2235\u20132247."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of COLT. PMLR, 228\u2013249","author":"Kolmogorov Vladimir","year":"2018","unstructured":"Vladimir Kolmogorov . 2018 . A faster approximation algorithm for the gibbs partition function . In Proceedings of COLT. PMLR, 228\u2013249 . Vladimir Kolmogorov. 2018. A faster approximation algorithm for the gibbs partition function. In Proceedings of COLT. PMLR, 228\u2013249."},{"key":"e_1_2_1_26_1","volume-title":"Levin and Yuval Peres","author":"David","year":"2017","unstructured":"David A. Levin and Yuval Peres . 2017 . Markov Chains and Mixing Times. American Mathematical Society . David A. Levin and Yuval Peres. 2017. Markov Chains and Mixing Times. American Mathematical Society."},{"key":"e_1_2_1_27_1","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal . 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis . Cambridge University Press . Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3268930"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516520"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.58.86"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"},{"key":"e_1_2_1_33_1","volume-title":"Mathematics and Computation: A Theory Revolutionizing Technology and Science","author":"Wigderson Avi","unstructured":"Avi Wigderson . 2019. Mathematics and Computation: A Theory Revolutionizing Technology and Science . Princeton University Press . Avi Wigderson. 2019. Mathematics and Computation: A Theory Revolutionizing Technology and Science. Princeton University Press."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3469832","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3469832","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:16Z","timestamp":1750188616000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3469832"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,5]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3469832"],"URL":"https:\/\/doi.org\/10.1145\/3469832","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,5]]},"assertion":[{"value":"2020-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}