{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:43Z","timestamp":1725488983602},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540001706"},{"type":"electronic","value":"9783540361695"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36169-3_8","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T04:27:32Z","timestamp":1186892852000},"page":"69-82","source":"Crossref","is-referenced-by-count":0,"title":["On Learning Embedded Midbit Functions"],"prefix":"10.1007","author":[{"given":"Rocco A.","family":"Servedio","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,11,8]]},"reference":[{"issue":"2","key":"8_CR1","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1006\/inco.1994.1057","volume":"112","author":"E. Allender","year":"1994","unstructured":"E. Allender and U. Hertrampf. Depth reduction for circuits of unbounded fan-in. Information and Computation, 112(2):217\u2013238, 1994.","journal-title":"Information and Computation"},{"issue":"1","key":"8_CR2","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. Barrington","year":"1989","unstructured":"D. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1. Journal of Computer and System Sciences, 38(1):150\u2013164, 1989.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"8_CR3","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D. Barrington","year":"1988","unstructured":"D. Barrington and D. Therien. Finite monoids and the fine structure of NC 1. J. ACM, 35(4):941\u2013952, 1988.","journal-title":"J. ACM"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/BF01263423","volume":"4","author":"R. Beigel","year":"1994","unstructured":"R. Beigel and J. Tarui. On ACC. Computational Complexity, 4:350\u2013366, 1994.","journal-title":"ACC. Computational Complexity"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Chalasani, and J. Jackson. On learning embedded symmetric concepts. In Proceedings of the Sixth Annual Conference on Computational Learning Theory, pages 337\u2013346, 1993.","DOI":"10.1145\/168304.168367"},{"issue":"4","key":"8_CR6","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929\u2013965, 1989.","journal-title":"Journal of the ACM"},{"issue":"1","key":"8_CR7","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0221014","volume":"21","author":"P. Fischer","year":"1992","unstructured":"P. Fischer and H.U. Simon. On learning ring-sum expansions. SIAM Journal on Computing, 21(1):181\u2013192, 1992.","journal-title":"SIAM Journal on Computing"},{"key":"8_CR8","volume-title":"Concrete Mathematics","author":"R. L. Graham","year":"1994","unstructured":"R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. Addison-Wesley, Reading, MA, 1994."},{"issue":"3","key":"8_CR9","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1006\/jcss.1995.1036","volume":"50","author":"F. Green","year":"1998","unstructured":"F. Green, J. Kobler, K. Regan, T. Schwentick, and J. Toran. The power of the middle bit of a #P function. Journal of Computer and System Sciences, 50(3):456\u2013467, 1998.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"8_CR10","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1137\/0221019","volume":"21","author":"D. Helmbold","year":"1992","unstructured":"D. Helmbold, R. Sloan, and M. Warmuth. Learning integer lattices. SIAM Journal on Computing, 21(2):240\u2013266., 1992.","journal-title":"SIAM Journal on Computing"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"A. Klivans and R. Servedio. Learning DNF in time 2\u00d5(n1\/3). In Proceedings of the Thirty-Third Annual Symposium on Theory of Computing, pages 258\u2013265, 2001.","DOI":"10.1145\/380752.380809"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"P. McKenzie and D. Therien. Automata theory meets circuit complexity. In Proceedings of the International Colloquium on Automata, Languages and Programming, pages 589\u2013602, 1989.","DOI":"10.1007\/BFb0035785"},{"key":"8_CR13","volume-title":"Perceptrons: an introduction to computational geometry","author":"M. Minsky","year":"1968","unstructured":"M. Minsky and S. Papert. Perceptrons: an introduction to computational geometry. MIT Press, Cambridge, MA, 1968."},{"key":"8_CR14","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1515\/crll.1834.11.353","volume":"11","author":"C. Ramus","year":"1834","unstructured":"C. Ramus. Solution g\u00e9n\u00e9rale d\u2019un probl\u00e8me d\u2019analyse combinatoire. J. Reine Agnew. Math., 11:353\u2013355, 1834.","journal-title":"J. Reine Agnew. Math."},{"key":"8_CR15","volume-title":"An Introduction to Combinatorial Analysis","author":"J. Riordan","year":"1958","unstructured":"J. Riordan. An Introduction to Combinatorial Analysis. Wiley, New York, 1958."},{"key":"8_CR16","volume-title":"Combinatorial Identities","author":"J. Riordan","year":"1968","unstructured":"J. Riordan. Combinatorial Identities. Wiley, New York, 1968."},{"issue":"11","key":"8_CR17","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. Valiant","year":"1984","unstructured":"L. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134\u20131142, 1984.","journal-title":"Communications of the ACM"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"A. Yao. Separating the polynomial time hierarchy by oracles. In Proceedings of the Twenty-Sixth Annual Symposium on Foundations of Computer Science, pages 1\u201310, 1985.","DOI":"10.1109\/SFCS.1985.49"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"A. Yao. On ACC and threshold circuits. In Proceedings of the Thirty-First Annual Symposium on Foundations of Computer Science, pages 619\u2013627, 1990.","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36169-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T23:40:31Z","timestamp":1556754031000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36169-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540001706","9783540361695"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-36169-3_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}