{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:03:36Z","timestamp":1746331416484,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_85","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"1027-1038","source":"Crossref","is-referenced-by-count":2,"title":["On Learning, Lower Bounds and (un)Keeping Promises"],"prefix":"10.1007","author":[{"given":"Ilya","family":"Volkovich","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"85_CR1","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D. Angluin","year":"1987","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput.\u00a075(2), 87\u2013106 (1987)","journal-title":"Inf. Comput."},{"key":"85_CR2","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":"85_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/3-540-45726-7_16","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"B. Barak","year":"2002","unstructured":"Barak, B.: A probabilistic-time hierarchy theorem for slightly non-uniform algorithms. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 194\u2013208. Springer, Heidelberg (2002)"},{"key":"85_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/3-540-49116-3_9","volume-title":"STACS 99","author":"H. Buhrman","year":"1999","unstructured":"Buhrman, H., Fortnow, L.: One-sided versus two-sided error in probabilistic computation. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 100\u2013109. Springer, Heidelberg (1999)"},{"key":"85_CR5","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Fortnow, L., Thierauf, T.: Nonrelativizing separations. In: Proceedings of the 13th Annual IEEE Conference on Computational Complexity (CCC), pp. 8\u201312 (1998)","DOI":"10.1109\/CCC.1998.694585"},{"issue":"1","key":"85_CR6","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.jcss.2008.07.006","volume":"75","author":"L. Fortnow","year":"2009","unstructured":"Fortnow, L., Klivans, A.R.: Efficient learning algorithms yield circuit lower bounds. J. Comput. Syst. Sci.\u00a075(1), 27\u201336 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"85_CR7","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Hierarchy theorems for probabilistic polynomial time. In: FOCS, pp. 316\u2013324 (2004)","DOI":"10.1109\/FOCS.2004.33"},{"key":"85_CR8","doi-asserted-by":"crossref","unstructured":"Gentry, C., Halevi, S.: Fully homomorphic encryption without squashing using depth-3 arithmetic circuits. In: Proceedings of the 52nd Annual FOCS, pp. 107\u2013109 (2011)","DOI":"10.1109\/FOCS.2011.94"},{"key":"85_CR9","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Zuckerman, D.: Another proof that bpp \u2286 ph (and more). In: Studies in Complexity and Cryptography, pp. 40\u201353 (2011)","DOI":"10.1007\/978-3-642-22670-0_6"},{"key":"85_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/978-3-642-22006-7_35","volume-title":"Automata, Languages and Programming","author":"R.C. Harkins","year":"2011","unstructured":"Harkins, R.C., Hitchcock, J.M.: Exact learning algorithms, betting games, and circuit lower bounds. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 416\u2013423. Springer, Heidelberg (2011)"},{"key":"85_CR11","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: Randomness vs. time: De-randomization under a uniform assumption. In: FOCS, pp. 734\u2013743 (1998)","DOI":"10.1109\/SFCS.1998.743524"},{"issue":"1-2","key":"85_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V. Kabanets","year":"2004","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity\u00a013(1-2), 1\u201346 (2004)","journal-title":"Computational Complexity"},{"issue":"1","key":"85_CR13","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M.J. Kearns","year":"1994","unstructured":"Kearns, M.J., Valiant, L.G.: Cryptographic limitations on learning boolean formulae and finite automata. J. ACM\u00a041(1), 67\u201395 (1994)","journal-title":"J. ACM"},{"key":"85_CR14","doi-asserted-by":"crossref","unstructured":"Klivans, A., Kothari, P., Oliveira, I.: Constructing hard functions from learning algorithms. In: Proceedings of the 28th Annual IEEE Conference on Computational Complexity (CCC), pp. 86\u201397 (2013)","DOI":"10.1109\/CCC.2013.18"},{"issue":"1","key":"85_CR15","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jcss.2008.07.008","volume":"75","author":"A.R. Klivans","year":"2009","unstructured":"Klivans, A.R., Sherstov, A.A.: Cryptographic hardness for learning intersections of halfspaces. J. Comput. Syst. Sci.\u00a075(1), 2\u201312 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"85_CR16","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00037-007-0227-8","volume":"16","author":"D. Melkebeek van","year":"2007","unstructured":"van Melkebeek, D., Pervyshev, K.: A generic time hierarchy with one bit of advice. Computational Complexity\u00a016(2), 139\u2013179 (2007)","journal-title":"Computational Complexity"},{"key":"85_CR17","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., Imai, H., Lee, D.T., Nakano, S.-i., Tokuyama, T. (eds.) COCOON 1999. LNCS, vol.\u00a01627, pp. 210\u2013220. Springer, Heidelberg (1999)"},{"issue":"2","key":"85_CR18","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/972639.972643","volume":"51","author":"M. Naor","year":"2004","unstructured":"Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. J. ACM\u00a051(2), 231\u2013262 (2004)","journal-title":"J. ACM"},{"issue":"1","key":"85_CR19","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A.A. Razboeov","year":"1997","unstructured":"Razboeov, A.A., Rudich, S.: Natural proofs. J. of Computer and System Sciences\u00a055(1), 24\u201335 (1997)","journal-title":"J. of Computer and System Sciences"},{"issue":"3","key":"85_CR20","doi-asserted-by":"publisher","first-page":"1038","DOI":"10.1137\/070702680","volume":"39","author":"R. Santhanam","year":"2009","unstructured":"Santhanam, R.: Circuit lower bounds for merlin\u2013arthur classes. SIAM J. Comput.\u00a039(3), 1038\u20131061 (2009)","journal-title":"SIAM J. Comput."},{"key":"85_CR21","unstructured":"Shamir, A.: IP=PSPACE. In: Proceedings of the Thirty First Annual Symposium on Foundations of Computer Science, pp. 11\u201315 (1990)"},{"issue":"4","key":"85_CR22","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s00037-007-0233-x","volume":"16","author":"L. Trevisan","year":"2007","unstructured":"Trevisan, L., Vadhan, S.P.: Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity\u00a016(4), 331\u2013364 (2007)","journal-title":"Computational Complexity"},{"issue":"11","key":"85_CR23","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Communications of the ACM\u00a027(11), 1134\u20131142 (1984)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_85","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:31:09Z","timestamp":1746264669000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_85"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_85","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}