{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T23:10:33Z","timestamp":1740265833837,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540265566"},{"type":"electronic","value":"9783540318927"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11503415_39","type":"book-chapter","created":{"date-parts":[[2010,7,14]],"date-time":"2010-07-14T22:16:38Z","timestamp":1279145798000},"page":"576-590","source":"Crossref","is-referenced-by-count":2,"title":["On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions"],"prefix":"10.1007","author":[{"given":"Vitaly","family":"Feldman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"39_CR1","first-page":"32","volume":"50","author":"A. Blum","year":"1995","unstructured":"Blum, A., Hellerstein, L., Littlestone, N.: Learning in the presence of finitely or infinitely many irrelevant attributes. JCSS\u00a050, 32\u201340 (1995)","journal-title":"JCSS"},{"key":"39_CR2","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1162\/153244302760200669","volume":"2","author":"N. Bshouty","year":"2002","unstructured":"Bshouty, N., Feldman, V.: On using extended statistical queries to avoid membership queries. Journal of Machince Learning Research\u00a02, 359\u2013395 (2002)","journal-title":"Journal of Machince Learning Research"},{"key":"39_CR3","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1006\/jcss.1998.1571","volume":"56","author":"N. Bshouty","year":"1998","unstructured":"Bshouty, N., Hellerstein, L.: Attribute efficient learning with queries. Journal of Computer and System Sciences\u00a056, 310\u2013319 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"39_CR4","doi-asserted-by":"crossref","unstructured":"Bshouty, N., Jackson, J., Tamon, C.: More efficient PAC learning of DNF with membership queries under the uniform distribution. In: Proceedings of COLT 1999, pp. 286\u2013295 (1999)","DOI":"10.1145\/307400.307472"},{"key":"39_CR5","doi-asserted-by":"crossref","unstructured":"Bshouty, N., Mossel, E., O\u2019Donnell, R., Servedio, R.: Learning DNF from random walks. In: Proceedings of FOCS 2003, pp. 189\u2013199 (2003)","DOI":"10.1109\/SFCS.2003.1238193"},{"key":"39_CR6","first-page":"590","volume-title":"Proceedings of STOC 1998","author":"P. Damaschke","year":"1998","unstructured":"Damaschke, P.: Adaptive versus nonadaptive attribute-efficient learning. In: Proceedings of STOC 1998, pp. 590\u2013596. ACM Press, New York (1998)"},{"key":"39_CR7","unstructured":"Farach, M., Kannan, S., Knill, E., Muthukrishnan, S.: Group testing problems in experimental molecular biology. In: Proceedings of Sequences 1997 (1997)"},{"key":"39_CR8","doi-asserted-by":"crossref","unstructured":"Freund, Y.: Boosting a weak learning algorithm by majority. In: Proceedings of the Third Annual Workshop on Computational Learning Theory, pp. 202\u2013216 (1990)","DOI":"10.1016\/B978-1-55860-146-8.50019-9"},{"key":"39_CR9","doi-asserted-by":"crossref","unstructured":"Freund, Y.: An improved boosting algorithm and its implications on learning complexity. In: Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pp. 391\u2013398 (1992)","DOI":"10.1145\/130385.130429"},{"key":"39_CR10","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Levin, L.: A hard-core predicate for all one-way functions. In: Proceedings of STOC 1989, pp. 25\u201332 (1989)","DOI":"10.1145\/73007.73010"},{"key":"39_CR11","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/3-540-49097-3_8","volume-title":"Computational Learning Theory","author":"D. Guijarro","year":"1999","unstructured":"Guijarro, D., Lavin, V., Raghavan, V.: Exact learning when irrelevant variables abound. In: Fischer, P., Simon, H.U. (eds.) EuroCOLT 1999. LNCS (LNAI), vol.\u00a01572, pp. 91\u2013100. Springer, Heidelberg (1999)"},{"key":"39_CR12","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/3-540-46769-6_26","volume-title":"Algorithmic Learning Theory","author":"D. Guijarro","year":"1999","unstructured":"Guijarro, D., Tarui, J., Tsukiji, T.: Finding relevant variables in PAC model with membership queries. In: Watanabe, O., Yokomori, T. (eds.) ALT 1999. LNCS (LNAI), vol.\u00a01720, pp. 313\u2013322. Springer, Heidelberg (1999)"},{"key":"39_CR13","doi-asserted-by":"crossref","unstructured":"Jackson, J.: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. In: Proceedings of STOC 1994, pp. 42\u201353 (1994)","DOI":"10.1109\/SFCS.1994.365706"},{"key":"39_CR14","unstructured":"Jackson, J.: Personal communication (2004)"},{"key":"39_CR15","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1109\/ISTCS.1997.595156","volume-title":"Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems","author":"J. Jackson","year":"1997","unstructured":"Jackson, J., Shamir, E., Shwartzman, C.: Learning with queries corrupted by classification noise. In: Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems, p. 45. IEEE Computer Society, Los Alamitos (1997)"},{"issue":"3","key":"39_CR16","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1023\/A:1022949332276","volume":"51","author":"A. Klivans","year":"2003","unstructured":"Klivans, A., Servedio, R.: Boosting and hard-core set construction. Machine Learning\u00a051(3), 217\u2013238 (2003)","journal-title":"Machine Learning"},{"key":"39_CR17","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-540-27819-1_16","volume-title":"Learning Theory","author":"A. Klivans","year":"2004","unstructured":"Klivans, A., Servedio, R.: Toward attribute efficient learning of decision lists and parities. In: Shawe-Taylor, J., Singer, Y. (eds.) COLT 2004. LNCS (LNAI), vol.\u00a03120, pp. 224\u2013238. Springer, Heidelberg (2004)"},{"issue":"3","key":"39_CR18","first-page":"1102","volume":"58","author":"L. Levin","year":"1993","unstructured":"Levin, L.: Randomness and non-determinism. Journal of Symbolic Logic\u00a058(3), 1102\u20131103 (1993)","journal-title":"Journal of Symbolic Logic"},{"key":"39_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/3-540-62685-9_15","volume-title":"Computational Learning Theory","author":"R. Uehara","year":"1997","unstructured":"Uehara, R., Tsuchida, K., Wegener, I.: Optimal attribute-efficient learning of disjunction, parity, and threshold functions. In: Ben-David, S. (ed.) EuroCOLT 1997. LNCS, vol.\u00a01208, pp. 171\u2013184. Springer, Heidelberg (1997)"},{"issue":"11","key":"39_CR20","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. Valiant","year":"1984","unstructured":"Valiant, L.: A theory of the learnable. Communications of the ACM\u00a027(11), 1134\u20131142 (1984)","journal-title":"Communications of the ACM"},{"key":"39_CR21","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195089264.001.0001","volume-title":"Circuits of the Mind","author":"L. Valiant","year":"1994","unstructured":"Valiant, L.: Circuits of the Mind. Oxford University Press, Oxford (1994)"},{"issue":"5","key":"39_CR22","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1145\/355483.355486","volume":"47","author":"L. Valiant","year":"2000","unstructured":"Valiant, L.: A neuroidal architecture for cognitive computation. Journal of ACM\u00a047(5), 854\u2013882 (2000)","journal-title":"Journal of ACM"},{"key":"39_CR23","unstructured":"Valiant, L.: Knowledge infusion (2005) (unpublished manuscript)"}],"container-title":["Lecture Notes in Computer Science","Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11503415_39.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T22:32:39Z","timestamp":1740263559000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11503415_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540265566","9783540318927"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11503415_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}