{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:23:00Z","timestamp":1725664980936},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540626855"},{"type":"electronic","value":"9783540684312"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-62685-9_2","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:47:23Z","timestamp":1330278443000},"page":"3-15","source":"Crossref","is-referenced-by-count":0,"title":["Learning boxes in high dimension"],"prefix":"10.1007","author":[{"given":"Amos","family":"Beimel","sequence":"first","affiliation":[]},{"given":"Eyal","family":"Kushilevitz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"issue":"4","key":"2_CR1","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"D. Angluin. Queries and concept learning. Machine Learning, 2(4):319\u2013342, 1988.","journal-title":"Machine Learning"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"P. Auer. On-line learning of rectangles in noisy environments. In Proc. of 6th Annu. ACM Workshop on Comput. Learning Theory, pages 253\u2013261, 1993.","DOI":"10.1145\/168304.168345"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"A. Beimel, F. Bergadano, N. H. Bshouty, E. Kushilevitz, and S. Varricchio. On the applications of multiplicity automata in learning. In Proc. of 37th Annu. IEEE Symp. on Foundations of Computer Science, pages 349\u2013358, 1996.","DOI":"10.1109\/SFCS.1996.548494"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"S. Ben-David, N. H. Bshouty, and E. Kushilevitz. A composition theorem for learning algorithms with applications to geometric concept classes. manuscript, 1996.","DOI":"10.1145\/258533.258614"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"F. Bergadano, D. Catalano, and S. Varricchio. Learning sat-k-DNF formulas from membership queries. In Proc. of 28th Annu. ACM Symp. on the Theory of Computing, pages 126\u2013130, 1996.","DOI":"10.1145\/237814.237845"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"A. Blum and S. Rudich. Fast learning of k-term DNF formulas with queries. In Proc. of 24th ACM Symp. on Theory of Computing, pages 382\u2013389, 1992.","DOI":"10.1145\/129712.129748"},{"key":"2_CR7","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36:929\u2013965, 1989.","journal-title":"Journal of the ACM"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty. Exact learning via the monotone theory. In Proc. of 34th Annu. IEEE Symp. on Foundations of Computer Science, pages 302\u2013311, 1993. Journal version: Information and Computation, 123(1):146\u2013153, 1995.","DOI":"10.1006\/inco.1995.1164"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty. Simple learning algorithms using divide and conquer. In Proc. of 8th Annu. ACM Workshop on Comput. Learning Theory, pages 447\u2013453, 1995.","DOI":"10.1145\/225298.225352"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty, Z. Chen, and S. Homer. On learning discretized geometric concepts. In Proc. of 35th Annu. Symp. on Foundations of Computer Science, pages 54\u201363, 1994.","DOI":"10.1109\/SFCS.1994.365705"},{"key":"2_CR11","unstructured":"N. H. Bshouty, P. W. Goldberg, S. A. Goldman, and H. D. Mathias. Exact learning of discretized geometric concepts. Technical Report WUCS-94-19, Washington University, 1994."},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty, S. A. Goldman, H. D. Mathias, S. Suri, and H. Tamaki. Noisetolerant distribution-free learning of general geometric concepts. In Proc. of 28th Annu. ACM Symp. on Theory of Computing, pages 151\u2013160, 1996.","DOI":"10.1145\/237814.237854"},{"issue":"2","key":"2_CR13","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0168-0072(95)00019-4","volume":"77","author":"Z. Chen","year":"1996","unstructured":"Z. Chen and S. Homer. The bounded injury priority method and the learnability of unions of rectangles. Annals of Pure and Applied Logic, 77(2):143\u2013168, 1996.","journal-title":"Annals of Pure and Applied Logic"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Z. Chen and W. Maass. On-line learning of rectangles. In Proc. of 5th Annu. ACM Workshop on Comput. Learning Theory, 1992.","DOI":"10.1145\/130385.130387"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"P. W. Goldberg, S. A. Goldman, and H. D. Mathias. Learning unions of boxes with membership and equivalence queries. In Proc. of 7th Annu. ACM Workshop on Comput. Learning Theory, 1994.","DOI":"10.1145\/180139.181102"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"J. C. Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. In 35th Annu. Symp. on Foundations of Computer Science, pages 42\u201353, 1994.","DOI":"10.1109\/SFCS.1994.365706"},{"key":"2_CR17","unstructured":"J. C. Jackson. The Harmonic Sieve: A Novel Application of Fourier Analysis to Machine Learning Theory and Practice. PhD thesis, Technical Report CMU-CS-95-184, School of Computer Science, Carnegie Mellon University, 1995."},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz. A simple algorithm for learning O(log n)-term DNF. In Proc. of 9th Annu. ACM Workshop on Comput. Learning Theory, pages 266\u2013269, 1996.","DOI":"10.1145\/238061.238115"},{"key":"2_CR19","first-page":"285","volume":"2","author":"N. Littlestone","year":"1988","unstructured":"N. Littlestone. Learning when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285\u2013318, 1988.","journal-title":"Machine Learning"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"P. M. Long and M. K. Warmuth. Composite geometric concepts and polynomial predictability. In Proc. of 3rd Annu. ACM Workshop on Comput. Learning Theory, pages 273\u2013287, 1990.","DOI":"10.1016\/B978-1-55860-146-8.50024-2"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"W. Maass and G. Turan. On the complexity of learning from counterexamples. In Proc. of 30th Annu. Symp. on Foundations of Computer Science, pages 262\u2013273, 1989.","DOI":"10.1109\/SFCS.1989.63488"},{"key":"2_CR22","first-page":"251","volume":"14","author":"W. Maass","year":"1994","unstructured":"W. Maass and G. Turan. Algorithms and lower bounds for on-line learning of geometrical concepts. Machine Learning, 14:251\u2013269, 1994.","journal-title":"Machine Learning"},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"W. Maass and M. K. Warmuth. Efficient learning with virtual threshold gates. In Proc. 12th International Conference on Machine Learning, pages 378\u2013386. Morgan Kaufmann, 1995.","DOI":"10.1016\/B978-1-55860-377-6.50054-2"},{"issue":"11","key":"2_CR24","doi-asserted-by":"crossref","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. Communications of the ACM, 27(11):1134\u20131142, 1984.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Computational Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-62685-9_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:13:53Z","timestamp":1605629633000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-62685-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540626855","9783540684312"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-62685-9_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}