{"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":1725471314977},"publisher-location":"Berlin, Heidelberg","reference-count":25,"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_27","type":"book-chapter","created":{"date-parts":[[2006,9,28]],"date-time":"2006-09-28T14:49:15Z","timestamp":1159454955000},"page":"350-363","source":"Crossref","is-referenced-by-count":5,"title":["Efficient Learning Algorithms Yield Circuit Lower Bounds"],"prefix":"10.1007","author":[{"given":"Lance","family":"Fortnow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam R.","family":"Klivans","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"Pitt, L., Valiant, L.: Computational limitations on learning from examples. Journal of the ACM\u00a035, 965\u2013984 (1988)","journal-title":"Journal of the ACM"},{"key":"27_CR2","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"E.A. Gold","year":"1978","unstructured":"Gold, E.A.: Complexity of automaton identification from given data. Information and Control\u00a037, 302\u2013320 (1978)","journal-title":"Information and Control"},{"key":"27_CR3","unstructured":"Alekhnovich, Braverman, Feldman, Klivans, Pitassi: Learnability and automatizability. In: FOCS: IEEE Symposium on Foundations of Computer Science (FOCS) (2004)"},{"key":"27_CR4","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M. Kearns","year":"1994","unstructured":"Kearns, M., Valiant, L.: Cryptographic limitations on learning Boolean formulae and finite automata. Journal of the ACM\u00a041, 67\u201395 (1994)","journal-title":"Journal of the ACM"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"Kharitonov, M.: Cryptographic hardness of distribution-specific learning. In: Proceedings of the Twenty-Fifth Annual Symposium on Theory of Computing, pp. 372\u2013381 (1993)","DOI":"10.1145\/167088.167197"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"Jackson, J., Klivans, A., Servedio, R.: Learnability beyond AC 0. In: Proceedings of the 34th ACM Symposium on Theory of Computing (2002)","DOI":"10.1145\/510014.510018"},{"key":"27_CR7","first-page":"355","volume-title":"Proceedings of the 35th ACM Symposium on the Theory of Computing","author":"V. Kabanets","year":"2003","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. In: Proceedings of the 35th ACM Symposium on the Theory of Computing, pp. 355\u2013364. ACM, New York (2003)"},{"key":"27_CR8","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1006\/jcss.2001.1780","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Wigderson, A.: Randomness vs. time: Derandomization under a uniform assumption. Journal of Computer and System Sciences\u00a063, 672\u2013688 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR9","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, 1134\u20131142 (1984)","journal-title":"Communications of the ACM"},{"key":"27_CR10","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":"27_CR11","first-page":"8","volume-title":"Proceedings of the 13th IEEE Conference on Computational Complexity","author":"H. Buhrman","year":"1998","unstructured":"Buhrman, H., Fortnow, L., Thierauf, T.: Nonrelativizing separations. In: Proceedings of the 13th IEEE Conference on Computational Complexity, pp. 8\u201312. IEEE, New York (1998)"},{"key":"27_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/3-540-48686-0_21","volume-title":"Computing and Combinatorics","author":"P.B. Miltersen","year":"1999","unstructured":"Miltersen, P.B., Vinodchandran, N.V., Watanabe, O.: Super-polynomial versus half-exponential circuit size in the exponential hierarchy. In: Asano, T., et al. (eds.) COCOON 1999. LNCS, vol.\u00a01627, p. 210. Springer, Heidelberg (1999)"},{"key":"27_CR13","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"Hartmanis, J., Stearns, R.: On the computational complexity of algorithms. Transactions of the American Mathematical Society\u00a0117, 285\u2013306 (1965)","journal-title":"Transactions of the American Mathematical Society"},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/S0019-9958(82)90382-5","volume":"55","author":"R. Kannan","year":"1982","unstructured":"Kannan, R.: Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control\u00a055, 40\u201356 (1982)","journal-title":"Information and Control"},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"Valiant, L.: The complexity of computing the permanent. Theoretical Computer Science\u00a08, 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing\u00a020, 865\u2013877 (1991)","journal-title":"SIAM Journal on Computing"},{"key":"27_CR17","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"191","volume-title":"Distributed Computing and Cryptography","author":"R. Lipton","year":"1991","unstructured":"Lipton, R.: New directions in testing. In: Feigenbaum, J., Merritt, M. (eds.) Distributed Computing and Cryptography. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a02, pp. 191\u2013202. American Mathematical Society, Providence (1991)"},{"key":"27_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-52282-4_30","volume-title":"STACS 90","author":"D. Beaver","year":"1990","unstructured":"Beaver, D., Feigenbaum, J.: Hiding instances in multioracle queries. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol.\u00a0415, pp. 37\u201348. Springer, Heidelberg (1990)"},{"key":"27_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/3-540-56287-7_99","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"H. Buhrman","year":"1992","unstructured":"Buhrman, H., Homer, S.: Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In: Shyamasundar, R.K. (ed.) FSTTCS 1992. LNCS, vol.\u00a0652, pp. 116\u2013127. Springer, Heidelberg (1992)"},{"key":"27_CR20","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity\u00a03, 307\u2013318 (1993)","journal-title":"Computational Complexity"},{"key":"27_CR21","doi-asserted-by":"crossref","unstructured":"Beimel, A., Bergadano, F., Bshouty, N., Kushilevitz, E., Varricchio, S.: On the applications of multiplicity automata in learning. In: Proceedings of the Thirty-Seventh Annual Symposium on Foundations of Computer Science, pp. 349\u2013358 (1996)","DOI":"10.1109\/SFCS.1996.548494"},{"key":"27_CR22","volume-title":"COLT: Proceedings of the Workshop on Computational Learning Theory","author":"Klivans","year":"2003","unstructured":"Klivans, Shpilka: Learning arithmetic circuits via partial derivatives. In: COLT: Proceedings of the Workshop on Computational Learning Theory. Morgan Kaufmann Publishers, San Francisco (2003)"},{"key":"27_CR23","doi-asserted-by":"crossref","unstructured":"Bshouty, Hancock, Hellerstein: Learning arithmetic read-once formulas. SICOMP: SIAM Journal on Computing\u00a024 (1995)","DOI":"10.1137\/S009753979223664X"},{"key":"27_CR24","doi-asserted-by":"crossref","unstructured":"Bshouty.: On interpolating arithmetic read-once formulas with exponentiation. JCSS: Journal of Computer and System Sciences\u00a056 (1998)","DOI":"10.1006\/jcss.1997.1550"},{"key":"27_CR25","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, fourier transform, and learnability. Journal of the ACM\u00a040, 607\u2013620 (1993)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11776420_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:06:54Z","timestamp":1605643614000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11776420_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540352945","9783540352969"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11776420_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}