{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:35:14Z","timestamp":1725471314273},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540352945"},{"type":"electronic","value":"9783540352969"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11776420_18","type":"book-chapter","created":{"date-parts":[[2006,9,28]],"date-time":"2006-09-28T14:49:15Z","timestamp":1159454955000},"page":"214-228","source":"Crossref","is-referenced-by-count":2,"title":["DNF Are Teachable in the Average Case"],"prefix":"10.1007","author":[{"given":"Homin K.","family":"Lee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Wan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Braverman, M., Feldman, V., Klivans, A., Pitassi, T.: Learnability and automatizability. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 621\u2013630 (2004)","DOI":"10.1109\/FOCS.2004.36"},{"issue":"1","key":"18_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(94)00007-Z","volume":"61","author":"M. Anthony","year":"1995","unstructured":"Anthony, M., Brightwell, G., Shawe-Taylor, J.: On specifying Boolean functions by labelled examples. Discrete Applied Math.\u00a061(1), 1\u201325 (1995)","journal-title":"Discrete Applied Math."},{"key":"18_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1007\/11503415_45","volume-title":"Learning Theory","author":"F.J. Balbach","year":"2005","unstructured":"Balbach, F.J.: Teaching classes with high teaching dimension using few examples. In: Auer, P., Meir, R. (eds.) COLT 2005. LNCS, vol.\u00a03559, pp. 668\u2013683. Springer, Heidelberg (2005)"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Blum, A.: Learning a function of r relevant variables (open problem). In: Proc. 16th Annual COLT, pp. 731\u2013733 (2003)","DOI":"10.1007\/978-3-540-45167-9_54"},{"issue":"6","key":"18_CR5","doi-asserted-by":"publisher","first-page":"1909","DOI":"10.1137\/S009753979732058X","volume":"31","author":"N. Bshouty","year":"2002","unstructured":"Bshouty, N., Mansour, Y.: Simple Learning Algorithms for Decision Trees and Multivariate Polynomials. SIAM J. Comput.\u00a031(6), 1909\u20131925 (2002)","journal-title":"SIAM J. Comput."},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Cherniavsky, J., Statman, R.: Testing: An abstract approach. In: Proceedings of the 2nd Workshop on Software Testing (1988)","DOI":"10.1109\/WST.1988.5352"},{"issue":"1","key":"18_CR7","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/jcss.1995.1003","volume":"50","author":"S. Goldman","year":"1992","unstructured":"Goldman, S., Kearns, M.: On the complexity of teaching. Journal of Computer and System Sciences\u00a050(1), 20\u201331 (1992)","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"18_CR8","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1137\/0222062","volume":"22","author":"S. Goldman","year":"1993","unstructured":"Goldman, S., Rivest, R., Schapire, R.: Learning binary relations and total orders. SIAM Journal on Computing\u00a022(5), 1006\u20131034 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/3-540-49097-3_14","volume-title":"Computational Learning Theory","author":"C. Kuhlmann","year":"1999","unstructured":"Kuhlmann, C.: On teaching and learning intersection-closed concept classes. In: Fischer, P., Simon, H.U. (eds.) EuroCOLT 1999. LNCS, vol.\u00a01572, pp. 168\u2013182. Springer, Heidelberg (1999)"},{"issue":"2","key":"18_CR10","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/S0097-3165(96)80015-X","volume":"73","author":"E. Kushilevitz","year":"1996","unstructured":"Kushilevitz, E., Linial, N., Rabinovich, Y., Saks, M.: Witness sets for families of binary vectors. J. Combinatorial Theory\u00a073(2), 376\u2013380 (1996)","journal-title":"J. Combinatorial Theory"},{"key":"18_CR11","unstructured":"Lee, H., Servedio, R., Wan, A.: DNF are Teachable in the Average Case (full version), available at: http:\/\/www.cs.columbia.edu\/~rocco\/papers\/dnfteach.html"},{"issue":"3","key":"18_CR12","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1016\/j.jcss.2004.04.002","volume":"69","author":"E. Mossel","year":"2004","unstructured":"Mossel, E., O\u2019Donnell, R., Servedio, R.: Learning functions of k relevant variables. J. Comput. & Syst. Sci.\u00a069(3), 421\u2013434 (2004)","journal-title":"J. Comput. & Syst. Sci."},{"issue":"2","key":"18_CR13","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1137\/0220019","volume":"20","author":"R. Roth","year":"1991","unstructured":"Roth, R., Benedek, G.: Interpolation and approximation of sparse multivariate polynomials over GF(2). SIAM J. Comput.\u00a020(2), 291\u2013314 (1991)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"18_CR14","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1006\/jcss.1996.0017","volume":"52","author":"R. Schapire","year":"1996","unstructured":"Schapire, R., Sellie, L.: Learning sparse multivariate polynomials over a field with queries and counterexamples. J. Comput. & Syst. Sci.\u00a052(2), 201\u2013213 (1996)","journal-title":"J. Comput. & Syst. Sci."},{"issue":"3","key":"18_CR15","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1109\/18.6031","volume":"34","author":"G. Seroussi","year":"1988","unstructured":"Seroussi, G., Bshouty, N.: Vector sets for exhaustive testing of logic circuits. IEEE Trans. on Information Theory\u00a034(3), 513\u2013522 (1988)","journal-title":"IEEE Trans. on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11776420_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:06:51Z","timestamp":1605643611000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11776420_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540352945","9783540352969"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/11776420_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}