{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T05:34:29Z","timestamp":1740548069702,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540282396"},{"type":"electronic","value":"9783540318743"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11538462_29","type":"book-chapter","created":{"date-parts":[[2010,9,28]],"date-time":"2010-09-28T04:13:22Z","timestamp":1285647202000},"page":"342-353","source":"Crossref","is-referenced-by-count":3,"title":["On Learning Random DNF Formulas Under the Uniform Distribution"],"prefix":"10.1007","author":[{"given":"Jeffrey C.","family":"Jackson","sequence":"first","affiliation":[]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"29_CR1","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":"29_CR2","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D.: Queries and concept learning. Machine Learning\u00a02, 319\u2013342 (1988)","journal-title":"Machine Learning"},{"key":"29_CR3","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1006\/jcss.1995.1026","volume":"50","author":"D. Angluin","year":"1995","unstructured":"Angluin, D., Kharitonov, M.: When won\u2019t membership queries help? J. Comput. & Syst. Sci.\u00a050, 336\u2013355 (1995)","journal-title":"J. Comput. & Syst. Sci."},{"key":"29_CR4","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/978-3-540-45167-9_54","volume-title":"Learning Theory and Kernel Machines","author":"A. Blum","year":"2003","unstructured":"Blum, A.: Learning a function of r relevant variables (open problem). In: Sch\u00f6lkopf, B., Warmuth, M.K. (eds.) COLT\/Kernel 2003. LNCS (LNAI), vol.\u00a02777, pp. 731\u2013733. Springer, Heidelberg (2003)"},{"doi-asserted-by":"crossref","unstructured":"Blum, A.: Machine learning: a tour through some favorite results, directions, and open problems. FOCS 2003 tutorial slides (2003), available at http:\/\/www-2.cs.cmu.edu\/~avrim\/Talks\/FOCS03\/tutorial.ppt","key":"29_CR5","DOI":"10.1109\/SFCS.2003.1238174"},{"doi-asserted-by":"crossref","unstructured":"Blum, A., Burch, C., Langford, J.: On learning monotone boolean functions. In: Proc. 39th FOCS, pp. 408\u2013415 (1998)","key":"29_CR6","DOI":"10.1109\/SFCS.1998.743491"},{"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)","key":"29_CR7","DOI":"10.1145\/195058.195147"},{"key":"29_CR8","volume-title":"Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability","author":"B. Bollobas","year":"1986","unstructured":"Bollobas, B.: Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability. Cambridge University Press, Cambridge (1986)"},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0893-6080(95)00009-7","volume":"9","author":"M. Golea","year":"1994","unstructured":"Golea, M., Marchand, M., Hancock, T.: On learning \u03bc-perceptron networks on the uniform distribution. Neural Networks\u00a09, 67\u201382 (1994)","journal-title":"Neural Networks"},{"doi-asserted-by":"crossref","unstructured":"Hancock, T.: Learning k\u03bc decision trees on the uniform distribution. In: Proc. Sixth COLT, pp. 352\u2013360 (1993)","key":"29_CR10","DOI":"10.1145\/168304.168374"},{"key":"29_CR11","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1006\/jcss.1997.1533","volume":"55","author":"J. Jackson","year":"1997","unstructured":"Jackson, J.: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. J. Comput. & Syst. Sci.\u00a055, 414\u2013440 (1997)","journal-title":"J. Comput. & Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Jackson, J., Klivans, A., Servedio, R.: Learnability beyond ACo. In: Proc. 34th STOC (2002)","key":"29_CR12","DOI":"10.1145\/510014.510018"},{"key":"29_CR13","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1007\/978-3-540-45167-9_44","volume-title":"Learning Theory and Kernel Machines","author":"J. Jackson","year":"2003","unstructured":"Jackson, J., Servedio, R.: Learning random log-depth decision trees under the uniform distribution. In: Sch\u00f6lkopf, B., Warmuth, M.K. (eds.) COLT\/Kernel 2003. LNCS (LNAI), vol.\u00a02777, pp. 610\u2013624. Springer, Heidelberg (2003)"},{"unstructured":"Jackson, J., Tamon, C.: Fourier analysis in machine learning. ICML\/COLT 1997 tutorial slides (1997), available at http:\/\/learningtheory.org\/resources.html","key":"29_CR14"},{"issue":"6","key":"29_CR15","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1145\/293347.293351","volume":"45","author":"M. Kearns","year":"1998","unstructured":"Kearns, M.: Efficient noise-tolerant learning from statistical queries. Journal of the ACM\u00a045(6), 983\u20131006 (1998)","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Kearns, M., Li, M., Pitt, L., Valiant, L.: Recent results on Boolean concept learning. In: Proc. Fourth Int. Workshop on Mach. Learning, pp. 337\u2013352 (1987)","key":"29_CR16","DOI":"10.1016\/B978-0-934613-41-5.50037-4"},{"key":"29_CR17","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)"},{"doi-asserted-by":"crossref","unstructured":"Klivans, A., O\u2019Donnell, R., Servedio, R.: Learning intersections and thresholds of halfspaces. In: Proc. 43rd FOCS, pp. 177\u2013186 (2002)","key":"29_CR18","DOI":"10.1109\/SFCS.2002.1181894"},{"key":"29_CR19","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1006\/inco.1994.1024","volume":"110","author":"L. Kucera","year":"1994","unstructured":"Kucera, L., Marchetti-Spaccamela, A., Protassi, M.: On learning monotone DNF formulae under uniform distributions. Inform. and Comput.\u00a0110, 84\u201395 (1994)","journal-title":"Inform. and Comput."},{"doi-asserted-by":"crossref","unstructured":"McDiarmid, C.: On the method of bounded differences. In: Surveys in Combinatoric 1989. London Mathematical Society Lecture Notes, pp. 148\u2013188 (1989)","key":"29_CR20","DOI":"10.1017\/CBO9781107359949.008"},{"key":"29_CR21","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/3-540-44581-1_31","volume-title":"Computational Learning Theory","author":"R. Servedio","year":"2001","unstructured":"Servedio, R.: On learning monotone DNF under product distributions. In: Helmbold, D.P., Williamson, B. (eds.) COLT 2001 and EuroCOLT 2001. LNCS (LNAI), vol.\u00a02111, pp. 473\u2013489. Springer, Heidelberg (2001)"},{"issue":"11","key":"29_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"},{"doi-asserted-by":"crossref","unstructured":"Verbeurgt, K.: Learning DNF under the uniform distribution in quasi-polynomial time. In: Proc. Third COLT, pp. 314\u2013326 (1990)","key":"29_CR23","DOI":"10.1016\/B978-1-55860-146-8.50027-8"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11538462_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T03:06:34Z","timestamp":1740539194000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11538462_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540282396","9783540318743"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11538462_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}