{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:09Z","timestamp":1750220529273,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451067","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"467-480","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Hardness of learning DNFs using halfspaces"],"prefix":"10.1145","author":[{"given":"Suprovat","family":"Ghoshal","sequence":"first","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rishi","family":"Saket","sequence":"additional","affiliation":[{"name":"IBM Research, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060628"},{"key":"e_1_3_2_1_2_1","volume-title":"The complexity of properly learning simple concept classes. J. Comput. System Sci., 74, 1","author":"Alekhnovich Misha","year":"2008","unstructured":"Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R Klivans, and Toniann Pitassi. 2008. The complexity of properly learning simple concept classes. J. Comput. System Sci., 74, 1, 2008. Pages 16\u201334."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.35"},{"key":"e_1_3_2_1_4_1","volume-title":"Lower bounds for DNF-refutations of a relativized weak pigeonhole principle. The Journal of Symbolic Logic, 80, 2","author":"Atserias Albert","year":"2015","unstructured":"Albert Atserias, Moritz M\u00fcller, and Sergi Oliva. 2015. Lower bounds for DNF-refutations of a relativized weak pigeonhole principle. The Journal of Symbolic Logic, 80, 2, 2015. Pages 450\u2013476."},{"key":"e_1_3_2_1_5_1","series-title":"SIAM J. Comput., 38, 6","volume-title":"Polylogarithmic independence can fool DNF formulas","author":"Bazzi Louay MJ","year":"2009","unstructured":"Louay MJ Bazzi. 2009. Polylogarithmic independence can fool DNF formulas. SIAM J. Comput., 38, 6, 2009. Pages 2220\u20132272."},{"key":"e_1_3_2_1_6_1","first-page":"917","volume-title":"Conference On Learning Theory, COLT 2018","author":"Bhattacharyya Arnab","year":"2018","unstructured":"Arnab Bhattacharyya, Suprovat Ghoshal, and Rishi Saket. 2018. Hardness of Learning Noisy Halfspaces using Polynomial Thresholds. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018.. Pages 876\u2013917."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Avrim Blum Merrick Furst Jeffrey Jackson Michael Kearns Yishay Mansour and Steven Rudich. 1994. Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In STOC. 94 Pages 253\u2013262.","DOI":"10.1145\/195058.195147"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238193"},{"key":"e_1_3_2_1_9_1","volume-title":"A subexponential exact learning algorithm for DNF using equivalence queries. Inform. Process. Lett., 59, 1","author":"Bshouty Nader H","year":"1996","unstructured":"Nader H Bshouty. 1996. A subexponential exact learning algorithm for DNF using equivalence queries. Inform. Process. Lett., 59, 1, 1996. Pages 37\u201339."},{"key":"e_1_3_2_1_10_1","volume-title":"Conference on Learning Theory. Pages 815\u2013830","author":"Daniely Amit","year":"2016","unstructured":"Amit Daniely and Shai Shalev-Shwartz. 2016. Complexity theoretic limitations on learning DNF\u2019s. In Conference on Learning Theory. Pages 815\u2013830."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806763"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.123"},{"key":"e_1_3_2_1_13_1","volume-title":"On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc., 51, 12","author":"Erd\u00f6s Paul","year":"1945","unstructured":"Paul Erd\u00f6s. 1945. On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc., 51, 12, 1945. Pages 898\u2013902."},{"key":"e_1_3_2_1_14_1","first-page":"236","volume-title":"Optimal Hardness Results for Maximizing Agreements with Monomials. In IEEE CCC","author":"Feldman Vitaly","year":"2006","unstructured":"Vitaly Feldman. 2006. Optimal Hardness Results for Maximizing Agreements with Monomials. In IEEE CCC 2006. Pages 226\u2013236."},{"key":"e_1_3_2_1_15_1","volume-title":"Hardness of approximate two-level logic minimization and PAC learning with membership queries. J. Comput. Syst. Sci., 75, 1","author":"Feldman Vitaly","year":"2009","unstructured":"Vitaly Feldman. 2009. Hardness of approximate two-level logic minimization and PAC learning with membership queries. J. Comput. Syst. Sci., 75, 1, 2009. Pages 13\u201326."},{"key":"e_1_3_2_1_16_1","volume-title":"Conference on Learning Theory. Pages 17\u20131.","author":"Feldman Vitaly","year":"2012","unstructured":"Vitaly Feldman. 2012. Learning DNF expressions from Fourier spectrum. In Conference on Learning Theory. Pages 17\u20131."},{"key":"e_1_3_2_1_17_1","series-title":"SIAM J. Comput., 39, 2","volume-title":"On Agnostic Learning of Parities, Monomials, and Halfspaces","author":"Feldman Vitaly","year":"2009","unstructured":"Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. 2009. On Agnostic Learning of Parities, Monomials, and Halfspaces. SIAM J. Comput., 39, 2, 2009. Pages 606\u2013645."},{"key":"e_1_3_2_1_18_1","series-title":"SIAM J. Comput., 41, 6","volume-title":"Agnostic learning of monomials by halfspaces is hard","author":"Feldman Vitaly","year":"2012","unstructured":"Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, and Yi Wu. 2012. Agnostic learning of monomials by halfspaces is hard. SIAM J. Comput., 41, 6, 2012. Pages 1558\u20131590."},{"key":"e_1_3_2_1_19_1","volume-title":"Hardness of Learning DNFs using Halfspaces. arXiv preprint arXiv:1911.06358","author":"Ghoshal Suprovat","year":"2019","unstructured":"Suprovat Ghoshal and Rishi Saket. 2019. Hardness of Learning DNFs using Halfspaces. arXiv preprint arXiv:1911.06358, 2019."},{"key":"e_1_3_2_1_20_1","volume-title":"DNF sparsification and a faster deterministic counting algorithm. Computational Complexity, 22, 2","author":"Gopalan Parikshit","year":"2013","unstructured":"Parikshit Gopalan, Raghu Meka, and Omer Reingold. 2013. DNF sparsification and a faster deterministic counting algorithm. Computational Complexity, 22, 2, 2013. Pages 275\u2013310."},{"key":"e_1_3_2_1_21_1","unstructured":"Lee-Ad Gottlieb Eran Kaufman Aryeh Kontorovich and Gabriel Nivasch. 2018. Learning convex polytopes with margin. In Advances in Neural Information Processing Systems. Pages 5706\u20135716."},{"key":"e_1_3_2_1_22_1","series-title":"SIAM J. Comput., 39, 2","volume-title":"Hardness of Learning Halfspaces with Noise","author":"Guruswami Venkatesan","year":"2009","unstructured":"Venkatesan Guruswami and Prasad Raghavendra. 2009. Hardness of Learning Halfspaces with Noise. SIAM J. Comput., 39, 2, 2009. Pages 742\u2013765."},{"key":"e_1_3_2_1_23_1","unstructured":"Isabelle Guyon Steve Gunn Asa Ben-Hur and Gideon Dror. 2005. Result analysis of the NIPS 2003 feature selection challenge. In Advances in neural information processing systems. Pages 545\u2013552."},{"key":"e_1_3_2_1_24_1","volume-title":"An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. J. Comput. System Sci., 55, 3","author":"Jackson Jeffrey C","year":"1997","unstructured":"Jeffrey C Jackson. 1997. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. J. Comput. System Sci., 55, 3, 1997. Pages 414\u2013440."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.60"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.37"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374426"},{"key":"e_1_3_2_1_28_1","first-page":"380","volume-title":"True for Random DNF Formulas. In COLT 2010 - The 23rd Conference on Learning Theory","author":"Klivans Adam R.","year":"2010","unstructured":"Adam R. Klivans, Homin K. Lee, and Andrew Wan. [n.d.]. Mansour's Conjecture is True for Random DNF Formulas. In COLT 2010 - The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010. Pages 368\u2013380."},{"key":"e_1_3_2_1_29_1","volume-title":"Learning intersections and thresholds of halfspaces. J. Comput. System Sci., 68, 4","author":"Klivans Adam R","year":"2004","unstructured":"Adam R Klivans, Ryan O'Donnell, and Rocco A Servedio. 2004. Learning intersections and thresholds of halfspaces. J. Comput. System Sci., 68, 4, 2004. Pages 808\u2013840."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.007"},{"key":"e_1_3_2_1_31_1","volume-title":"Cryptographic hardness for learning intersections of halfspaces. J. Comput. System Sci., 75, 1","author":"Klivans Adam R","year":"2009","unstructured":"Adam R Klivans and Alexander A Sherstov. 2009. Cryptographic hardness for learning intersections of halfspaces. J. Comput. System Sci., 75, 1, 2009. Pages 2\u201312."},{"key":"e_1_3_2_1_32_1","first-page":"311","volume-title":"Learning Talagrand DNF Formulas. In COLT 2010 - The 23rd Conference on Learning Theory","author":"Lee Homin K.","year":"2010","unstructured":"Homin K. Lee. 2010. Learning Talagrand DNF Formulas. In COLT 2010 - The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010. Pages 310\u2013311."},{"key":"e_1_3_2_1_33_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM","author":"Li Xin","year":"2018","unstructured":"Xin Li, Shachar Lovett, and Jiapeng Zhang. 2018. Sunflowers and quasi-sunflowers from randomness extractors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2018)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316323"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49381-6_26"},{"volume-title":"Analysis of boolean functions","author":"O'Donnell Ryan","key":"e_1_3_2_1_36_1","unstructured":"Ryan O'Donnell. 2014. Analysis of boolean functions. Cambridge University Press."},{"key":"e_1_3_2_1_37_1","volume-title":"Computational limitations on learning from examples. Journal of the ACM (JACM), 35, 4","author":"Pitt Leonard","year":"1988","unstructured":"Leonard Pitt and Leslie G Valiant. 1988. Computational limitations on learning from examples. Journal of the ACM (JACM), 35, 4, 1988. Pages 965\u2013984."},{"key":"e_1_3_2_1_38_1","volume-title":"The perceptron: a probabilistic model for information storage and organization in the brain.. Psychological review, 65, 6","author":"Rosenblatt Frank","year":"1958","unstructured":"Frank Rosenblatt. 1958. The perceptron: a probabilistic model for information storage and organization in the brain.. Psychological review, 65, 6, 1958. Pages 386."},{"key":"e_1_3_2_1_39_1","series-title":"SIAM J. Comput., 33, 5","volume-title":"A switching lemma for small restrictions and lower bounds for k-DNF resolution","author":"Segerlind Nathan","year":"2004","unstructured":"Nathan Segerlind, Sam Buss, and Russell Impagliazzo. 2004. A switching lemma for small restrictions and lower bounds for k-DNF resolution. SIAM J. Comput., 33, 5, 2004. Pages 1171\u20131200."},{"key":"e_1_3_2_1_40_1","volume-title":"On learning monotone DNF under product distributions. Information and Computation, 193, 1","author":"Servedio Rocco A","year":"2004","unstructured":"Rocco A Servedio. 2004. On learning monotone DNF under product distributions. Information and Computation, 193, 1, 2004. Pages 57\u201374."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.18"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808710"},{"key":"e_1_3_2_1_43_1","unstructured":"Vladimir Vapnik. 1998. Statistical learning theory."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/92571.92659"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451067","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451067","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451067"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":44,"alternative-id":["10.1145\/3406325.3451067","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451067","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}