{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:05Z","timestamp":1750695005160,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","funder":[{"name":"National Science Foundation","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Office of Naval Research","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718262","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"2055-2061","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["DNF Learning via Locally Mixing Random Walks"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-2204-1359","authenticated-orcid":false,"given":"Josh","family":"Alman","sequence":"first","affiliation":[{"name":"Columbia University, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1825-6122","authenticated-orcid":false,"given":"Shivam","family":"Nadimpalli","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9174-9139","authenticated-orcid":false,"given":"Shyamal","family":"Patel","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2407-543X","authenticated-orcid":false,"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/291511.291512"},{"key":"e_1_3_2_1_2_1","first-page":"179","volume-title":"32nd Annual Symposium on Foundations of Computer Science","author":"Aizenstein Howard","year":"1991","unstructured":"Howard Aizenstein and Leonard Pitt. Exact learning of read-twice DNF formulas (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 170\u2013179, 1991."},{"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\/337244.337257"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/168304.168309"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293123"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/307400.307472"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.010"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1075"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1164"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00077-4"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01262930"},{"key":"e_1_3_2_1_13_1","first-page":"497","volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms","author":"De Anindya","unstructured":"Anindya De, Ilias Diakonikolas, and Rocco A Servedio. Learning from satisfying assignments. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 478\u2013497. SIAM, 2014."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007627028578"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1162\/153244304322765667"},{"key":"e_1_3_2_1_16_1","first-page":"209","volume-title":"Proceedings of the Fourth Annual Workshop on Computational Learning Theory","author":"Hancock T.","year":"1991","unstructured":"T. Hancock. Learning 2\u03bc DNF formulas and k \u03bc decision trees. In Proceedings of the Fourth Annual Workshop on Computational Learning Theory, pages 199\u2013209, 1991."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90042-Z"},{"key":"e_1_3_2_1_18_1","first-page":"193","volume-title":"Proceedings of the Fourth Annual Conference on Computational Learning Theory","author":"Hancock T.","year":"1991","unstructured":"T. Hancock and Y. Mansour. Learning monotone k-\u03bc DNF formulas on product distributions. In Proceedings of the Fourth Annual Conference on Computational Learning Theory, pages 179\u2013193, 1991."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1533"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.08.022"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a008"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45655-4_63"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90057-4"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488611"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1024"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/168304.168362"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022949332276"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.007"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00026-4"},{"key":"e_1_3_2_1_30_1","volume-title":"Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):1\u201330","author":"Lee James R","year":"2014","unstructured":"James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):1\u201330, 2014."},{"key":"e_1_3_2_1_31_1","volume-title":"Locally stationary distributions: A framework for analyzing slow-mixing markov chains. arXiv preprint arXiv:2405.20849","author":"Liu Kuikui","year":"2024","unstructured":"Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman, and David X Wu. Locally stationary distributions: A framework for analyzing slow-mixing markov chains. arXiv preprint arXiv:2405.20849, 2024."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214079"},{"key":"e_1_3_2_1_33_1","volume-title":"A greedy method for learning \u03bc-DNF functions under the uniform distribution. Technical report","author":"Pagallo Giulia","year":"1989","unstructured":"Giulia Pagallo and David Haussler. A greedy method for learning \u03bc-DNF functions under the uniform distribution. Technical report, University of California at Santa Cruz, UCSC-CRL-89-12, 1989."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1149"},{"key":"e_1_3_2_1_35_1","first-page":"192","volume-title":"Proc. 21st Colt","author":"Sellie L.","year":"2008","unstructured":"L. Sellie. Learning Random Monotone DNF Under the Uniform Distribution. In Proc. 21st Colt, pages 181\u2013192, 2008."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536424"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.04.003"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910002"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/080744888"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1999.766279"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_1_42_1","first-page":"326","volume-title":"Conference on Learning Theory","author":"Verbeurgt Karsten A.","unstructured":"Karsten A. Verbeurgt. Learning DNF under the uniform distribution in quasi-polynomial time. In Mark A. Fulk, editor, Conference on Learning Theory, pages 314\u2013326. Morgan Kaufmann, 1990."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49730-7_27"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718262","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:47:00Z","timestamp":1750693620000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718262"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":43,"alternative-id":["10.1145\/3717823.3718262","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718262","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}