{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T13:08:43Z","timestamp":1783170523900,"version":"3.54.6"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T00:00:00Z","timestamp":1554422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000008","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1453261 and CCF-1565235"],"award-info":[{"award-number":["CCF-1453261 and CCF-1565235"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>In this article, we introduce a new approach to approximate counting in bounded degree systems with higher-order constraints. Our main result is an algorithm to approximately count the number of solutions to a CNF formula \u03a6 when the width is logarithmic in the maximum degree. This closes an exponential gap between the known upper and lower bounds.<\/jats:p>\n          <jats:p>Moreover, our algorithm extends straightforwardly to approximate sampling, which shows that under Lov\u00e1sz Local Lemma-like conditions it is not only possible to find a satisfying assignment, it is also possible to generate one approximately uniformly at random from the set of all satisfying assignments. Our approach is a significant departure from earlier techniques in approximate counting, and is based on a framework to bootstrap an oracle for computing marginal probabilities on individual variables. Finally, we give an application of our results to show that it is algorithmically possible to sample from the posterior distribution in an interesting class of graphical models.<\/jats:p>","DOI":"10.1145\/3268930","type":"journal-article","created":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T13:37:23Z","timestamp":1554730643000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Approximate Counting, the Lov\u00e1sz Local Lemma, and Inference in Graphical Models"],"prefix":"10.1145","volume":"66","author":[{"given":"Ankur","family":"Moitra","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,4,5]]},"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","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","author":"Bez\u00e1kova I.","year":"2016"},{"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.1137\/100796029"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/100799642"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(93)90036-B"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00013-1"},{"key":"e_1_2_1_10_1","unstructured":"P. Erd\u00f6s and L. Lov\u00e1sz. 1975. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets. North Holland 609--627.  P. Erd\u00f6s and L. Lov\u00e1sz. 1975. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets. North Holland 609--627."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000401"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2010.10.002"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055410"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188934"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049702"},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"A constructive algorithm for the Lov\u00e1sz Local Lemma on permutations. In Theor","volume":"13","author":"Harris D.","year":"2017","journal-title":"Comput."},{"key":"e_1_2_1_17_1","volume-title":"LLL. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)","author":"Harvey N."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.85"},{"key":"e_1_2_1_19_1","first-page":"07999","article-title":"Rapid mixing of hypergraph independent set","volume":"1610","author":"Hermon J.","year":"2016","journal-title":"ArXiv"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","volume-title":"The Art of Computer Programming","author":"Knuth D.","DOI":"10.1145\/1283920.1283929"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.88"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Liu J."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_2_1_25_1","unstructured":"C. Nair and P. Tetali. 2007. The correlation decay (CD) tree and strong spatial mixing in multi-spin systems. ArXiv:0701494.  C. Nair and P. Tetali. 2007. The correlation decay (CD) tree and strong spatial mixing in multi-spin systems. ArXiv:0701494."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-014-0947-5"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOP888"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3268930","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3268930","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3268930","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:19Z","timestamp":1750212439000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3268930"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,5]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3268930"],"URL":"https:\/\/doi.org\/10.1145\/3268930","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,5]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}