{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:08Z","timestamp":1750220768380,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":27,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007515","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1614023,1763299"],"award-info":[{"award-number":["1614023,1763299"]}],"id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384241","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"247-254","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","author":[{"given":"Shachar","family":"Lovett","sequence":"first","affiliation":[{"name":"University of California at San Diego, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kewen","family":"Wu","sequence":"additional","affiliation":[{"name":"Peking University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiapeng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"volume-title":"Improved bounds for the sunflower lemma. arXiv preprint arXiv","year":"1908","author":"Alweiss Ryan","key":"e_1_3_2_1_1_1"},{"doi-asserted-by":"crossref","unstructured":"Vikraman Arvind Johannes K\u00f6bler Sebastian Kuhnert Gaurav Rattan and Yadu Vasudev. 2015. On the isomorphism problem for decision trees and decision lists. Theoretical Computer Science 590 ( 2015 ) 38-54.  Vikraman Arvind Johannes K\u00f6bler Sebastian Kuhnert Gaurav Rattan and Yadu Vasudev. 2015. On the isomorphism problem for decision trees and decision lists. Theoretical Computer Science 590 ( 2015 ) 38-54.","key":"e_1_3_2_1_2_1","DOI":"10.1016\/j.tcs.2015.01.025"},{"doi-asserted-by":"crossref","unstructured":"Giulia Bagallo and David Haussler. 1990. Boolean feature discovery in empirical learning. Machine learning 5 1 ( 1990 ) 71-99.  Giulia Bagallo and David Haussler. 1990. Boolean feature discovery in empirical learning. Machine learning 5 1 ( 1990 ) 71-99.","key":"e_1_3_2_1_3_1","DOI":"10.1007\/BF00115895"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1016\/0020-0190(92)90237-P"},{"volume-title":"Lower Bounds for Linear Decision Lists. CoRR abs\/","year":"1901","author":"Chattopadhyay Arkadev","key":"e_1_3_2_1_6_1"},{"doi-asserted-by":"crossref","unstructured":"Andrzej Ehrenfeucht David Haussler Michael Kearns and Leslie Valiant. 1989. A general lower bound on the number of examples needed for learning. Information and Computation 82 3 ( 1989 ) 247-261.  Andrzej Ehrenfeucht David Haussler Michael Kearns and Leslie Valiant. 1989. A general lower bound on the number of examples needed for learning. Information and Computation 82 3 ( 1989 ) 247-261.","key":"e_1_3_2_1_7_1","DOI":"10.1016\/0890-5401(89)90002-3"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.1016\/S0304-3975(01)00003-2"},{"doi-asserted-by":"crossref","unstructured":"Ehud Friedgut. 1998. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18 1 ( 1998 ) 27-35.  Ehud Friedgut. 1998. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18 1 ( 1998 ) 27-35.","key":"e_1_3_2_1_9_1","DOI":"10.1007\/PL00009809"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.1007\/s00037-013-0068-6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1016\/S0304-3975(00)00043-8"},{"doi-asserted-by":"crossref","unstructured":"Thomas Hancock Tao Jiang Ming Li and John Tromp. 1996. Lower bounds on learning decision lists and trees. Information and Computation 126 2 ( 1996 ) 114-122.  Thomas Hancock Tao Jiang Ming Li and John Tromp. 1996. Lower bounds on learning decision lists and trees. Information and Computation 126 2 ( 1996 ) 114-122.","key":"e_1_3_2_1_12_1","DOI":"10.1006\/inco.1996.0040"},{"volume-title":"Computational Limitations of Small-depth Circuits","author":"H\u00e5stad Johan","key":"e_1_3_2_1_13_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.1006\/jcss.1997.1533"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1145\/28395.28426"},{"doi-asserted-by":"crossref","unstructured":"Adam R Klivans and Rocco A Servedio. 2003. Boosting and hard-core set construction. Machine Learning 51 3 ( 2003 ) 217-238.  Adam R Klivans and Rocco A Servedio. 2003. Boosting and hard-core set construction. Machine Learning 51 3 ( 2003 ) 217-238.","key":"e_1_3_2_1_16_1","DOI":"10.1023\/A:1022949332276"},{"doi-asserted-by":"crossref","unstructured":"Ron Kohavi and Scott Benson. 1993. Research note on decision lists. Machine Learning 13 1 ( 1993 ) 131-134.  Ron Kohavi and Scott Benson. 1993. Research note on decision lists. Machine Learning 13 1 ( 1993 ) 131-134.","key":"e_1_3_2_1_17_1","DOI":"10.1007\/BF00993105"},{"doi-asserted-by":"crossref","unstructured":"Matthias Krause. 2006. On the computational power of Boolean decision lists. computational complexity 14 4 ( 2006 ) 362-375.  Matthias Krause. 2006. On the computational power of Boolean decision lists. computational complexity 14 4 ( 2006 ) 362-375.","key":"e_1_3_2_1_18_1","DOI":"10.1007\/s00037-005-0203-0"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1145\/3313276.3316323"},{"key":"e_1_3_2_1_20_1","article-title":"On online learning of decision lists","author":"Nevo Ziv","year":"2002","journal-title":"Journal of Machine Learning Research 3"},{"volume-title":"Analysis of boolean functions","author":"O'Donnell Ryan","doi-asserted-by":"crossref","key":"e_1_3_2_1_21_1","DOI":"10.1017\/CBO9781139814782"},{"volume-title":"Bounded arithmetic and lower bounds in Boolean complexity","author":"Razborov Alexander A","key":"e_1_3_2_1_22_1"},{"doi-asserted-by":"crossref","unstructured":"Alexander A Razborov. 2015. Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution. Annals of Mathematics ( 2015 ) 415-472.  Alexander A Razborov. 2015. Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution. Annals of Mathematics ( 2015 ) 415-472.","key":"e_1_3_2_1_23_1","DOI":"10.4007\/annals.2015.181.2.1"},{"doi-asserted-by":"crossref","unstructured":"Ronald L Rivest. 1987. Learning decision lists. Machine learning 2 3 ( 1987 ) 229-246.  Ronald L Rivest. 1987. Learning decision lists. Machine learning 2 3 ( 1987 ) 229-246.","key":"e_1_3_2_1_24_1","DOI":"10.1007\/BF00058680"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.1137\/S0097539703428555"},{"volume-title":"Foundations of Computational Mathematics","author":"Tur\u00e1n Gy\u00f6rgy","key":"e_1_3_2_1_26_1"},{"key":"e_1_3_2_1_27_1","first-page":"1013","article-title":"Falling rule lists","author":"Wang Fulton","year":"2015","journal-title":"Artificial Intelligence and Statistics."},{"volume-title":"Data Mining: Practical machine learning tools and techniques. Morgan Kaufmann.","year":"2016","author":"Witten Ian H","key":"e_1_3_2_1_28_1"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '20","name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA"},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384241","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384241","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384241"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":27,"alternative-id":["10.1145\/3357713.3384241","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384241","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}