{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:38:00Z","timestamp":1725489480206},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414131"},{"type":"electronic","value":"9783540444503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44450-5_27","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T04:26:08Z","timestamp":1187238368000},"page":"336-347","source":"Crossref","is-referenced-by-count":0,"title":["On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation"],"prefix":"10.1007","author":[{"given":"Johannes","family":"K\u00f6bler","sequence":"first","affiliation":[]},{"given":"Wolfgang","family":"Lindner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,11,24]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"D. Angluin and M. Kharitonov. When won\u2019t membership queries help? In Proc. 23rd ACM Symposium on Theory of Computing, pages 444\u2013454. ACM Press, 1991.","DOI":"10.1145\/103418.103420"},{"key":"27_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1007\/3-540-48329-2_24","volume-title":"Cryptographicpri mitives based on hard learning problems","author":"A. Blum","year":"1994","unstructured":"A. Blum, M. Furst, M. Kearns, and R. J. Lipton. Cryptographicpri mitives based on hard learning problems. In Proc. CRYPTO 93, volume 773 of Lecture Notes in Computer Science, pages 278\u2013291. Springer-Verlag, 1994."},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"A. L. Blum. Separating distribution-free and mistake-bound learning models over the boolean domain. In Proc. 31st IEEE Symposium on the Foundations of Computer Science, pages 211\u2013218. IEEE Computer Society Press, 1990.","DOI":"10.1109\/FSCS.1990.89540"},{"issue":"6","key":"27_CR4","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","volume":"24","author":"A. Blumer","year":"1987","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Occam\u2019s razor. Information Processing Letters, 24(6):377\u2013380, 1987.","journal-title":"Information Processing Letters"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"D. Boneh and R. J. Lipton. Amplification of weak learning under the uniform distribution. In Proc. 6th ACM Conference on Computational Learning Theory, pages 347\u2013351. ACM Press, 1993.","DOI":"10.1145\/168304.168372"},{"key":"27_CR6","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J. L. Carter","year":"1979","unstructured":"J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143\u2013154, 1979.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"27_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/BF02090764","volume":"23","author":"J. D\u00edaz","year":"1990","unstructured":"J. D\u00edaz and J. Tor\u00e1n. Classes of bounded nondeterminism. Mathematical Systems Theory, 23(1):21\u201332, 1990.","journal-title":"Mathematical Systems Theory"},{"issue":"4","key":"27_CR8","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O. Goldreich","year":"1986","unstructured":"O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. Journal of the ACM, 33(4):792\u2013807, 1986.","journal-title":"Journal of the ACM"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and A. Wigderson. Randomness vs. time: De-randomization under a uniform assumption. In Proc. 39th IEEE Symposium on the Foundations of Computer Science, pages 734\u2013743. IEEE Computer Society Press, 1998.","DOI":"10.1109\/SFCS.1998.743524"},{"issue":"3","key":"27_CR10","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1006\/jcss.1997.1533","volume":"55","author":"J. C. Jackson","year":"1997","unstructured":"J. C. Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. Journal of Computer and System Sciences, 55(3):414\u2013440, 1997.","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR11","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M. J. Kearns","year":"1994","unstructured":"M. J. Kearns and L. G. Valiant. Cryptographiclim itations on learning boolean formulae and finite automata. Journal of the ACM, 41:67\u201395, 1994.","journal-title":"Journal of the ACM"},{"key":"27_CR12","doi-asserted-by":"crossref","unstructured":"M. Kharitonov. Cryptographicha rdness of distribution-specific learning. In Proc. 25th ACM Symposium on Theory of Computing, pages 372\u2013381, 1993.","DOI":"10.1145\/167088.167197"},{"key":"27_CR13","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1006\/jcss.1995.1046","volume":"50","author":"M. Kharitonov","year":"1995","unstructured":"M. Kharitonov. Cryptographiclo wer bounds for learnability of boolean functions on the uniform distribution. Journal of Computer and System Sciences, 50:600\u2013610, 1995.","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR14","unstructured":"M. Krause and S. Lucks. On learning versus distinguishing and the minimal hardware complexity of pseudorandom function generators. Technical Report TR00-014, Electronic Colloquium on Computational Complexity, 2000."},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"W. Lindner, R. Schuler, and O. Watanabe. Resource-bounded measure and learnability. In Proc. 13th Annual IEEE Conference on Computational Complexity, pages 261\u2013270, 1998.","DOI":"10.1109\/CCC.1998.694620"},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J. H. Lutz","year":"1992","unstructured":"J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44:220\u2013258, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR17","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"N. Nisan and A. Wigderson. Hardness vs randomness. Journal of Computer and System Sciences, 49:149\u2013167, 1994.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"27_CR18","first-page":"197","volume":"5","author":"R. E. Schapire","year":"1990","unstructured":"R. E. Schapire. The strength of weak learnability. Machine Learning, 5(2):197\u2013226, 1990.","journal-title":"Machine Learning"},{"issue":"11","key":"27_CR19","doi-asserted-by":"publisher","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"},{"key":"27_CR20","doi-asserted-by":"crossref","unstructured":"A. C. Yao. Theory and applications of trapdoor functions. In Proc. 23rd IEEE Symposium on the Foundations of Computer Science, pages 80\u201391. IEEE Computer Society Press, 1982.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44450-5_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T00:16:52Z","timestamp":1556756212000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44450-5_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540414131","9783540444503"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-44450-5_27","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}