{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:51:11Z","timestamp":1781077871106,"version":"3.54.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["1614023"],"award-info":[{"award-number":["1614023"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whose term is satisfied by the input. Decision lists generalize both CNFs and DNFs and have been studied both in complexity theory and in learning theory.<\/jats:p>\n          <jats:p>The size of a decision list is the number of rules, and its width is the maximal number of variables in a term. We prove that decision lists of small width can always be approximated by decision lists of small size, where we obtain sharp bounds for such approximation. This also resolves a conjecture of Gopalan, Meka, and Reingold (Computational Complexity, 2013) on DNF sparsification.<\/jats:p>\n          <jats:p>An ingredient in our proof is a new random restriction lemma, which allows to analyze how DNFs (and more generally, decision lists) simplify if a small fraction of the variables are fixed. This is in contrast to the more commonly used switching lemma, which requires most of the variables to be fixed.<\/jats:p>","DOI":"10.1145\/3485007","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T17:40:31Z","timestamp":1635442831000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Decision List Compression by Mild Random Restrictions"],"prefix":"10.1145","volume":"68","author":[{"given":"Shachar","family":"Lovett","sequence":"first","affiliation":[{"name":"University of California, San Diego, La Jolla, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kewen","family":"Wu","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiapeng","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384234"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1026"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.01.025"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00115895"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90237-P"},{"key":"e_1_2_1_7_1","volume-title":"\u00c9tude des coefficients de Fourier des fonctions de . Annal. L\u2019inst. Fourier 20, 2","author":"Bonami Aline","year":"1970"},{"key":"e_1_2_1_8_1","unstructured":"Arkadev Chattopadhyay Meena Mahajan Nikhil S. Mande and Nitin Saurabh. 2020. Lower bounds for linear decision lists. (unpublished).  Arkadev Chattopadhyay Meena Mahajan Nikhil S. Mande and Nitin Saurabh. 2020. Lower bounds for linear decision lists. (unpublished)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90002-3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00003-2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-35.1.85"},{"key":"e_1_2_1_12_1","volume-title":"Efficiency and Computational Limitations of Learning Algorithms","author":"\u00a0al Vitaly Feldman"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009809"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 21st Annual Conference on Learning Theory (COLT\u201908)","author":"Gopalan Parikshit","year":"2008"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0068-6"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201912)","author":"Gopalan Parikshit","year":"2012"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00043-8"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0040"},{"key":"e_1_2_1_19_1","volume-title":"Computational Limitations of Small-depth Circuits","author":"H\u00e5stad Johan"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1533"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28426"},{"key":"e_1_2_1_22_1","first-page":"182","article-title":"An improved derandomization of the switching lemma","volume":"27","author":"Kelley Zander","year":"2020","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_2_1_23_1","volume-title":"DNF Formulas. In Proceedings of the 23rd Conference on Learning Theory (COLT\u201910)","author":"Klivans Adam R.","year":"2010"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022949332276"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993105"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0203-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316323"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1043"},{"key":"e_1_2_1_30_1","article-title":"On online learning of decision lists","author":"Nevo Ziv","year":"2002","journal-title":"J. Mach. Learn. Res. 3"},{"key":"e_1_2_1_31_1","volume-title":"Analysis of Boolean Functions","author":"O\u2019Donnell Ryan"},{"key":"e_1_2_1_32_1","volume-title":"Bounded arithmetic and lower bounds in boolean complexity","author":"Razborov Alexander A."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Alexander A. Razborov. 2015. Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution. Ann. Math. (2015) 415\u2013472.  Alexander A. Razborov. 2015. Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution. Ann. Math. (2015) 415\u2013472.","DOI":"10.4007\/annals.2015.181.2.1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022607331053"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703428555"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 32nd Computational Complexity Conference (CCC\u201917)","volume":"79","author":"Tal Avishay","year":"2017"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.32"},{"key":"e_1_2_1_38_1","volume-title":"Foundations of Computational Mathematics","author":"Tur\u00e1n Gy\u00f6rgy"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-55860-146-8.50027-8"},{"key":"e_1_2_1_40_1","unstructured":"Fulton Wang and Cynthia Rudin. 2015. Falling rule lists. In Artificial Intelligence and Statistics. 1013\u20131022.  Fulton Wang and Cynthia Rudin. 2015. Falling rule lists. In Artificial Intelligence and Statistics. 1013\u20131022."},{"key":"e_1_2_1_41_1","volume-title":"Pal","author":"Witten Ian H.","year":"2016"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485007","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485007","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485007","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:15Z","timestamp":1750191435000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485007"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,28]]},"references-count":40,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3485007"],"URL":"https:\/\/doi.org\/10.1145\/3485007","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,28]]},"assertion":[{"value":"2020-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}