{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:18Z","timestamp":1781031438519,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":67,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"ECS grant from Hong Kong SAR","award":["27202725"],"award-info":[{"award-number":["27202725"]}]},{"name":"National Natural Science Foundation of China","award":["62472212"],"award-info":[{"award-number":["62472212"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800766","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"478-488","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4636-1023","authenticated-orcid":false,"given":"Weiming","family":"Feng","sequence":"first","affiliation":[{"name":"University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0180-3695","authenticated-orcid":false,"given":"Xiongxin","family":"Yang","sequence":"additional","affiliation":[{"name":"University of California Santa Barbara, Santa Barbara, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-9222-4826","authenticated-orcid":false,"given":"Yixiao","family":"Yu","sequence":"additional","affiliation":[{"name":"Nanjing University, State Key Laboratory for Novel Software Technology, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8363-1219","authenticated-orcid":false,"given":"Yiyao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Nanjing University, State Key Laboratory for Novel Software Technology, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","unstructured":"D. Achlioptas and C. Moore. 2002. The asymptotic order of the random k-SAT threshold. In FOCS. 779\u2013788. https:\/\/doi.org\/10.1109\/SFCS.2002.1182003 10.1109\/SFCS.2002.1182003","DOI":"10.1109\/SFCS.2002.1182003"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","unstructured":"Dimitris Achlioptas and Yuval Peres. 2003. The threshold for random k-SAT is 2^k \u0142n 2 - O(k). In STOC. 223\u2013231. https:\/\/doi.org\/10.1145\/780542.780577 10.1145\/780542.780577","DOI":"10.1145\/780542.780577"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022697326858"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718262"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS63196.2025.00051"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992675"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.12.019"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/337244.337257"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1083906"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3094404"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3561047"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382207"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129748"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","unstructured":"Guy Bresler. 2015. Efficiently learning Ising models on arbitrary graphs. In STOC Rocco A. Servedio and Ronitt Rubinfeld (Eds.). 771\u2013782. https:\/\/doi.org\/10.1145\/2746539.2746631 10.1145\/2746539.2746631","DOI":"10.1145\/2746539.2746631"},{"key":"e_1_3_2_1_15_1","unstructured":"Guy Bresler David Gamarnik and Devavrat Shah. 2014. Structure learning of antiferromagnetic Ising models. In NeurIPS. 2852\u20132860."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/100796029"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366857"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01262930"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00077-4"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718232"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","unstructured":"Rohan Chauhan and Ioannis Panageas. 2026. Learning Ising models under hard constraints using one sample. In ICLR (to appear). https:\/\/doi.org\/10.48550\/arXiv.2509.20993 10.48550\/arXiv.2509.20993","DOI":"10.48550\/arXiv.2509.20993"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/23M1595722"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","unstructured":"Zongchen Chen Aditya Lonkar Chunyang Wang Kuan Yang and Yitong Yin. 2025. Counting random k-SAT near the satisfiability threshold. In STOC. 867\u2013878. https:\/\/doi.org\/10.1145\/3717823.3718163 10.1145\/3717823.3718163","DOI":"10.1145\/3717823.3718163"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054142"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","unstructured":"Amin Coja-Oghlan. 2014. The asymptotic k-SAT threshold. In STOC. 804\u2013813. https:\/\/doi.org\/10.1145\/2591796.2591822 10.1145\/2591796.2591822","DOI":"10.1145\/2591796.2591822"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471200611"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","unstructured":"Yuval Dagan Constantinos Daskalakis Nishanth Dikkala and Anthimos Vardis Kandiros. 2021. Learning Ising models from one or multiple samples. In STOC. 161\u2013168. https:\/\/doi.org\/10.1145\/3406325.3451074 10.1145\/3406325.3451074","DOI":"10.1145\/3406325.3451074"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.33"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2022.196.1.1"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90001-1"},{"key":"e_1_3_2_1_31_1","series-title":"Colloquia Mathematica Societatis J\u00e1nos Bolyai","volume-title":"Problems and results on 3-chromatic Hypergraphs and some related questions. 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. Infinite and finite sets, volume 10 of Colloquia Mathematica Societatis J\u00e1nos Bolyai, 609\u2013628."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469832"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","unstructured":"Weiming Feng Kun He and Yitong Yin. 2021. Sampling constraint satisfaction solutions in the local lemma regime. In STOC. 1565\u20131578. https:\/\/doi.org\/10.1145\/3406325.3451119 10.1145\/3406325.3451119","DOI":"10.1145\/3406325.3451119"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2507.15173"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","unstructured":"Jason Gaitonde Ankur Moitra and Elchanan Mossel. 2025. Bypassing the noisy parity barrier: learning higher-order Markov random fields from dynamics. In STOC. 348\u2013359. https:\/\/doi.org\/10.1145\/3717823.3718231 10.1145\/3717823.3718231","DOI":"10.1145\/3717823.3718231"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","unstructured":"Jason Gaitonde and Elchanan Mossel. 2024. A unified approach to learning Ising models: beyond independence and bounded width. In STOC. 503\u2013514. https:\/\/doi.org\/10.1145\/3618260.3649674 10.1145\/3618260.3649674","DOI":"10.1145\/3618260.3649674"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1351527"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2025.84"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","unstructured":"Andreas Galanis Alkis Kalavasis and Anthimos Vardis Kandiros. 2024. Learning hard-constrained models with one sample. In SODA. 3184\u20133196. https:\/\/doi.org\/10.1137\/1.9781611977912.115 10.1137\/1.9781611977912.115","DOI":"10.1137\/1.9781611977912.115"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049702"},{"key":"e_1_3_2_1_42_1","unstructured":"Linus Hamilton Frederic Koehler and Ankur Moitra. 2017. Information theoretic properties of Markov random fields and their algorithmic applications. In NeurIPS. 2463\u20132472."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2107.03932"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","unstructured":"Kun He Chunyang Wang and Yitong Yin. 2022. Sampling Lov\u00e1sz local lemma for general constraint satisfaction solutions in near-linear time. In FOCS. 147\u2013158. https:\/\/doi.org\/10.1109\/FOCS54457.2022.00021 10.1109\/FOCS54457.2022.00021","DOI":"10.1109\/FOCS54457.2022.00021"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","unstructured":"Kun He Chunyang Wang and Yitong Yin. 2023. Deterministic counting Lov\u00e1sz local lemma beyond linear programming. In SODA. 3388\u20133425. https:\/\/doi.org\/10.1137\/1.9781611977554.ch130 10.1137\/1.9781611977554.ch130","DOI":"10.1137\/1.9781611977554.ch130"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","unstructured":"Kun He Kewen Wu and Kuan Yang. 2023. Improved bounds for sampling solutions of random CNF formulas. In SODA. 3330\u20133361. https:\/\/doi.org\/10.1137\/1.9781611977554.ch128 10.1137\/1.9781611977554.ch128","DOI":"10.1137\/1.9781611977554.ch128"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3369930"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20830"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_29"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00025"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2102.08342"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/365411.365486"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.39"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.007"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00011-1"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3268930"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2023.106448"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2191659"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"crossref","unstructured":"Linda Sellie. 2008. Learning random monotone DNF under the uniform distribution. In COLT.","DOI":"10.1145\/1536414.1536424"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","unstructured":"Linda Sellie. 2009. Exact learning of random DNF over the uniform distribution. In STOC. 45\u201354. https:\/\/doi.org\/10.1145\/1536414.1536424 10.1145\/1536414.1536424","DOI":"10.1145\/1536414.1536424"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","unstructured":"Jun Tarui and Tatsuie Tsukiji. 1999. Learning DNF by approximating inclusion-exclusion formulae. In CCC. 215. https:\/\/doi.org\/10.1109\/CCC.1999.766279 10.1109\/CCC.1999.766279","DOI":"10.1109\/CCC.1999.766279"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_1_65_1","unstructured":"Marc Vuffray Sidhant Misra Andrey Lokhov and Michael Chertkov. 2016. Interaction screening: efficient and sample-optimal learning of Ising models. In NeurIPS. 29."},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","unstructured":"Chunyang Wang and Yitong Yin. 2024. A sampling Lov\u00e1sz local lemma for large domain sizes. In FOCS. 129\u2013150. https:\/\/doi.org\/10.1109\/FOCS61266.2024.00020 10.1109\/FOCS61266.2024.00020","DOI":"10.1109\/FOCS61266.2024.00020"},{"key":"e_1_3_2_1_67_1","volume-title":"Dimakis","author":"Wu Shanshan","year":"2019","unstructured":"Shanshan Wu, Sujay Sanghavi, and Alexandros G. Dimakis. 2019. Sparse logistic regression learns all discrete pairwise graphical models. In NeurIPS. 8069\u20138079."}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800766","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:01:01Z","timestamp":1781028061000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800766"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":67,"alternative-id":["10.1145\/3798129.3800766","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800766","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}