{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T05:04:18Z","timestamp":1737435858398,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540423430"},{"type":"electronic","value":"9783540445814"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44581-1_37","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:13:49Z","timestamp":1186740829000},"page":"558-573","source":"Crossref","is-referenced-by-count":2,"title":["On Learning Monotone DNF under Product Distributions"],"prefix":"10.1007","author":[{"given":"Rocco A.","family":"Servedio","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,13]]},"reference":[{"issue":"4","key":"37_CR1","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1145\/31846.31852","volume":"34","author":"M. Ajtai","year":"1987","unstructured":"M. Ajtai and Y. Gurevich. Monotone versus positive, J. ACM 34(4) (1987), 1004\u20131015.","journal-title":"J. ACM"},{"key":"37_CR2","unstructured":"P. Beame. A switching lemma primer. Tech. report UW-CSE-95-07-01, University of Washington, November 1994."},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"A. Beimel, F. Bergadano, N. Bshouty, E. Kushilevitz and S. Varricchio. On the applicationf of multiplicity automata in learning, in \u201cProc. 37th Ann. Symp. On Foundations of Computer Science\u201d (1996), 349\u2013358.","DOI":"10.1109\/SFCS.1996.548494"},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"A. Blum, M. Furst, J. Jackson, M. Kearns, Y. Mansour, and S. Rudich. Weakly learning DNF and characterizing statistical query learning using Fourier analysis, in \u201cProc. 26th Ann. Symp. on Theory of Computing\u201d (1994), 253\u2013262.","DOI":"10.1145\/195058.195147"},{"key":"37_CR5","unstructured":"R. Bahadur. A representation of the joint distribution of responses to n dichotomous items, in Herbert Solomon, ed., Studies in Item Analysis and Prediction, pp. 158\u2013168, Stanford University Press, 1961."},{"key":"37_CR6","doi-asserted-by":"crossref","unstructured":"M. Bellare. A technique for upper bounding the spectral norm with applications to learning, in \u201cProc. Fifth Ann. Workshop on Comp. Learning Theory\u201d (1992), 62\u201370.","DOI":"10.1145\/130385.130392"},{"issue":"3","key":"37_CR7","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.1995.1075","volume":"51","author":"A. Blum","year":"1995","unstructured":"A. Blum and S. Rudich. Fast learning of k-term DNF formulas with queries, J. Comp. Syst. Sci. 51(3) (1995), 367\u2013373.","journal-title":"J. Comp. Syst. Sci."},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"R. Boppana and M. Sipser. The complexity of finite functions, in Handbook of Theoretical Computer Science, vol. A, MIT Press, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"issue":"1","key":"37_CR9","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1006\/inco.1995.1164","volume":"123","author":"N. Bshouty","year":"1995","unstructured":"N. Bshouty. Exact learning via the monotone theory. Information and Computation 123(1) (1995), 146\u2013153.","journal-title":"Information and Computation"},{"key":"37_CR10","unstructured":"N. Bshouty. Simple learning algorithms using divide and conquer, Information Processing Letters"},{"key":"37_CR11","doi-asserted-by":"crossref","unstructured":"N. Bshouty, J. Jackson, and C. Tamon. More efficient PAC-learning of DNF with membership queries under the uniform distribution, in \u201cProc. 12th Ann. Conf. on Comp. Learning Theory\u201d (1999), 286\u2013295.","DOI":"10.1145\/307400.307472"},{"issue":"4","key":"37_CR12","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1145\/234533.234564","volume":"43","author":"N. Bshouty","year":"1996","unstructured":"N. Bshouty and C. Tamon. On the Fourier spectrum of monotone functions, J. ACM 43(4) (1996), 747\u2013770.","journal-title":"J. ACM"},{"key":"37_CR13","doi-asserted-by":"crossref","unstructured":"M. Furst, J. Jackson, and S. Smith. Improved learning of AC 0 functions, in \u201cProc. Fourth Ann. Workshop on Comp. Learning Theory\u201d (1991), 317\u2013325.","DOI":"10.1016\/B978-1-55860-213-7.50032-8"},{"key":"37_CR14","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","volume":"33","author":"T. Hagerup","year":"1989","unstructured":"T. Hagerup and C. Rub. A guided tour to Chernoff bounds, Inf. Proc. Lett. 33 (1989), 305\u2013308.","journal-title":"Inf. Proc. Lett."},{"key":"37_CR15","unstructured":"T. Hancock. The complexity of learning formulas and decision trees that have restricted reads, Ph.D. thesis, Harvard University, TR-15-92 (1992)."},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"T. Hancock and Y. Mansour. Learning monotone k-\u00b5 DNF formulas on product distributions, in \u201cProc. 4th Ann. Workshop on Comp. Learning Theory\u201d (1991), 179\u2013183.","DOI":"10.1016\/B978-1-55860-213-7.50020-1"},{"key":"37_CR17","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad. Computational Limitations for Small Depth Circuits. Ph.D. thesis, MIT Press, 1986.","DOI":"10.1145\/12130.12132"},{"key":"37_CR18","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1006\/jcss.1997.1533","volume":"55","author":"J. Jackson","year":"1997","unstructured":"J. Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, J. Comput. Syst. Sci. 55 (1997), 414\u2013440.","journal-title":"J. Comput. Syst. Sci."},{"key":"37_CR19","doi-asserted-by":"crossref","unstructured":"J. Kahn, G. Kalai, and N. Linial. The influence of variables on Boolean functions, in \u201cProc. 29th Ann. Symp. on Found. of Comp. Sci. \u201d (1988), 68\u201380.","DOI":"10.1109\/SFCS.1988.21923"},{"key":"37_CR20","doi-asserted-by":"crossref","unstructured":"M. Kearns, M. Li, L. Pitt, and L. Valiant. On the learnability of Boolean formulae, in \u201cProc. 19th Ann. ACM Symp. on Theory of Computing\u201d (1987), 285\u2013295.","DOI":"10.1145\/28395.28426"},{"issue":"6","key":"37_CR21","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1145\/195613.195656","volume":"41","author":"M. Kearns","year":"1994","unstructured":"M. Kearns, M. Li, and L. Valiant. Learning boolean formulas, J. ACM 41(6) (1994), 1298\u20131328.","journal-title":"J. ACM"},{"key":"37_CR22","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0020-0190(94)90057-4","volume":"49","author":"R. Khardon","year":"1994","unstructured":"R. Khardon. On using the Fourier transform to learn disjoint DNF, Information Processing Letters 49 (1994), 219\u2013222.","journal-title":"Information Processing Letters"},{"key":"37_CR23","doi-asserted-by":"crossref","unstructured":"A. Klivans and R. Servedio. Boosting and hard-core sets, in \u201cProc. 40th Ann. Symp. on Found. of Comp. Sci. \u201d (1999), 624\u2013633.","DOI":"10.1109\/SFFCS.1999.814638"},{"key":"37_CR24","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1006\/inco.1994.1024","volume":"110","author":"L. Kucera","year":"1994","unstructured":"L. Kucera, A. Marchetti-Spaccamela and M. Protassi. On learning monotone DNF formulae under uniform distributions, Inf. and Comput. 110 (1994), 84\u201395.","journal-title":"Inf. and Comput."},{"issue":"6","key":"37_CR25","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/S0020-0190(97)00026-4","volume":"61","author":"E. Kushilevitz","year":"1997","unstructured":"E. Kushilevitz. A simple algorithm for learing O(log n)-term DNF. Information Processing Letters 61(6) (1997), 289\u2013292.","journal-title":"Information Processing Letters"},{"issue":"3","key":"37_CR26","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"N. Linial, Y. Mansour and N. Nisan. Constant depth circuits, Fourier transform and learnability, J. ACM 40(3) (1993), 607\u2013620.","journal-title":"J. ACM"},{"key":"37_CR27","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1006\/jcss.1995.1043","volume":"50","author":"Y. Mansour","year":"1995","unstructured":"Y. Mansour. An O(n log log n) learning algorithm for DNF under the uniform distribution, J. Comput. Syst. Sci. 50 (1995), 543\u2013550.","journal-title":"J. Comput. Syst. Sci."},{"key":"37_CR28","first-page":"74","volume":"38","author":"E. Okolnishnikova","year":"1982","unstructured":"E. Okol\u2019nishnikova. On the influence of negations on the complexity of a realization of monotone Boolean functions by formulas of bounded depth, Metody Diskret. Analiz. 38 (1982), 74\u201380 (in Russian).","journal-title":"Metody Diskret. Analiz"},{"key":"37_CR29","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s002249910002","volume":"33","author":"Y. Sakai","year":"2000","unstructured":"Y. Sakai and A. Maruoka. Learning monotone log-term DNF formulas under the uniform distribution, Theory Comput. Systems 33 (2000), 17\u201333. A preliminary version appeared in \u201cProc. Seventh Conf. on Comp. Learning Theory\u201d (1994), 165-172.","journal-title":"Theory Comput. Systems"},{"issue":"11","key":"37_CR30","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"L.G. Valiant. A theory of the learnable, Comm. ACM 27(11) (1984), 1134\u20131142.","journal-title":"Comm. ACM"},{"key":"37_CR31","doi-asserted-by":"crossref","unstructured":"K. Verbeurgt. Learning DNF under the uniform distribution in quasi-polynomial time, in \u201cProc. 3rd Ann. Workshop on Comp. Learning Theory\u201d (1990), 314\u2013326.","DOI":"10.1016\/B978-1-55860-146-8.50027-8"},{"key":"37_CR32","doi-asserted-by":"crossref","unstructured":"K. Verbeurgt. Learning sub-classes of monotone DNF on the uniform distribution, in \u201cProc. 9th Conf. on Algorithmic Learning Theory\u201d (1998), 385\u2013399.","DOI":"10.1007\/3-540-49730-7_27"}],"container-title":["Lecture Notes in Computer Science","Computational Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44581-1_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T07:23:30Z","timestamp":1737357810000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44581-1_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540423430","9783540445814"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-44581-1_37","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}