{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:31:52Z","timestamp":1725517912949},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540853626"},{"type":"electronic","value":"9783540853633"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85363-3_38","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T15:29:28Z","timestamp":1219850968000},"page":"483-497","source":"Crossref","is-referenced-by-count":3,"title":["Learning Random Monotone DNF"],"prefix":"10.1007","author":[{"given":"Jeffrey C.","family":"Jackson","sequence":"first","affiliation":[]},{"given":"Homin K.","family":"Lee","sequence":"additional","affiliation":[]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[]},{"given":"Andrew","family":"Wan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"38_CR1","doi-asserted-by":"crossref","unstructured":"Amano, K., Maruoka, A.: On learning monotone boolean functions under the uniform distribution. In: Proc. 13th ALT, pp. 57\u201368 (2002)","DOI":"10.1007\/3-540-36169-3_7"},{"key":"38_CR2","first-page":"183","volume":"19","author":"H. Aizenstein","year":"1995","unstructured":"Aizenstein, H., Pitt, L.: On the learnability of disjunctive normal form formulas. Machine Learning\u00a019, 183\u2013208 (1995)","journal-title":"Machine Learning"},{"key":"38_CR3","doi-asserted-by":"crossref","unstructured":"Blum, A., Burch, C., Langford, J.: On learning monotone boolean functions. In: Proc. 39th FOCS, pp. 408\u2013415 (1998)","DOI":"10.1109\/SFCS.1998.743491"},{"key":"38_CR4","doi-asserted-by":"crossref","unstructured":"Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., Rudich, S.: Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In: Proc. 26th STOC, pp. 253\u2013262 (1994)","DOI":"10.1145\/195058.195147"},{"key":"38_CR5","doi-asserted-by":"crossref","unstructured":"Blum, A.: Learning a function of r relevant variables (open problem). In: Proc. 16th COLT, pp. 731\u2013733 (2003)","DOI":"10.1007\/978-3-540-45167-9_54"},{"key":"38_CR6","unstructured":"Blum, A.: Machine learning: a tour through some favorite results, directions, and open problems. In: FOCS 2003 tutorial slides (2003)"},{"issue":"4","key":"38_CR7","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1145\/234533.234564","volume":"43","author":"N. Bshouty","year":"1996","unstructured":"Bshouty, N., Tamon, C.: On the Fourier spectrum of monotone functions. Journal of the ACM\u00a043(4), 747\u2013770 (1996)","journal-title":"Journal of the ACM"},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"Hancock, T., Mansour, Y.: Learning monotone k-\u03bc DNF formulas on product distributions. In: Proc. 4th COLT, pp. 179\u2013193 (1991)","DOI":"10.1016\/B978-1-55860-213-7.50020-1"},{"key":"38_CR9","first-page":"414","volume":"55","author":"J. Jackson","year":"1997","unstructured":"Jackson, J.: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. JCSS\u00a055, 414\u2013440 (1997)","journal-title":"JCSS"},{"issue":"5","key":"38_CR10","doi-asserted-by":"crossref","first-page":"1107","DOI":"10.1137\/S0097539704444555","volume":"34","author":"J. Jackson","year":"2005","unstructured":"Jackson, J., Servedio, R.: Learning random log-depth decision trees under the uniform distribution. SICOMP\u00a034(5), 1107\u20131128 (2005)","journal-title":"SICOMP"},{"issue":"8","key":"38_CR11","doi-asserted-by":"publisher","first-page":"147","DOI":"10.4086\/toc.2006.v002a008","volume":"2","author":"J. Jackson","year":"2006","unstructured":"Jackson, J., Servedio, R.: On learning random DNF formulas under the uniform distribution. Theory of Computing\u00a02(8), 147\u2013172 (2006)","journal-title":"Theory of Computing"},{"key":"38_CR12","unstructured":"Jackson, J., Tamon, C.: Fourier analysis in machine learning. In: ICML\/COLT 1997 tutorial slides (1997)"},{"issue":"6","key":"38_CR13","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1145\/195613.195656","volume":"41","author":"M. Kearns","year":"1994","unstructured":"Kearns, M., Li, M., Valiant, L.: Learning Boolean formulas. Journal of the ACM\u00a041(6), 1298\u20131328 (1994)","journal-title":"Journal of the ACM"},{"key":"38_CR14","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1006\/inco.1994.1024","volume":"110","author":"L. Ku\u010dera","year":"1994","unstructured":"Ku\u010dera, L., Marchetti-Spaccamela, A., Protassi, M.: On learning monotone DNF formulae under uniform distributions. Information and Computation\u00a0110, 84\u201395 (1994)","journal-title":"Information and Computation"},{"key":"38_CR15","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An introduction to computational learning theory","author":"M. Kearns","year":"1994","unstructured":"Kearns, M., Vazirani, U.: An introduction to computational learning theory. MIT Press, Cambridge (1994)"},{"key":"38_CR16","first-page":"543","volume":"50","author":"Y. Mansour","year":"1995","unstructured":"Mansour, Y.: An O(n loglogn ) learning algorithm for DNF under the uniform distribution. JCSS\u00a050, 543\u2013550 (1995)","journal-title":"JCSS"},{"issue":"3","key":"38_CR17","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1002\/rsa.10097","volume":"23","author":"E. Mossel","year":"2003","unstructured":"Mossel, E., O\u2019Donnell, R.: On the noise sensitivity of monotone functions. Random Structures and Algorithms\u00a023(3), 333\u2013350 (2003)","journal-title":"Random Structures and Algorithms"},{"key":"38_CR18","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Servedio, R.: Learning monotone decision trees in polynomial time. In: Proc. 21st CCC, pp. 213\u2013225 (2006)","DOI":"10.1109\/CCC.2006.25"},{"key":"38_CR19","doi-asserted-by":"crossref","unstructured":"Sellie, L.: Learning Random Monotone DNF Under the Uniform Distribution. In: Proc. 21st COLT (to appear, 2008)","DOI":"10.1145\/1536414.1536424"},{"issue":"1","key":"38_CR20","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.ic.2004.04.003","volume":"193","author":"R. Servedio","year":"2004","unstructured":"Servedio, R.: On learning monotone DNF under product distributions. Information and Computation\u00a0193(1), 57\u201374 (2004)","journal-title":"Information and Computation"},{"key":"38_CR21","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s002249910002","volume":"33","author":"Y. Sakai","year":"2000","unstructured":"Sakai, Y., Maruoka, A.: Learning monotone log-term DNF formulas under the uniform distribution. Theory of Computing Systems\u00a033, 17\u201333 (2000)","journal-title":"Theory of Computing Systems"},{"issue":"11","key":"38_CR22","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. Valiant","year":"1984","unstructured":"Valiant, L.: A theory of the learnable. CACM\u00a027(11), 1134\u20131142 (1984)","journal-title":"CACM"},{"key":"38_CR23","doi-asserted-by":"crossref","unstructured":"Verbeurgt, K.: Learning DNF under the uniform distribution in quasi-polynomial time. In: Proc. 3rd COLT, pp. 314\u2013326 (1990)","DOI":"10.1016\/B978-1-55860-146-8.50027-8"},{"key":"38_CR24","doi-asserted-by":"crossref","unstructured":"Verbeurgt, K.: Learning sub-classes of monotone DNF on the uniform distribution. In: Proc. 9th ALT, pp. 385\u2013399 (1998)","DOI":"10.1007\/3-540-49730-7_27"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:24:20Z","timestamp":1606166660000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/10.1007\/978-3-540-85363-3_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540853626","9783540853633"],"references-count":24,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/978-3-540-85363-3_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}