{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T16:17:57Z","timestamp":1778689077607,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642161070","type":"print"},{"value":"9783642161087","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16108-7_18","type":"book-chapter","created":{"date-parts":[[2010,8,31]],"date-time":"2010-08-31T08:58:37Z","timestamp":1283245117000},"page":"194-208","source":"Crossref","is-referenced-by-count":3,"title":["Lower Bounds on Learning Random Structures with Statistical Queries"],"prefix":"10.1007","author":[{"given":"Dana","family":"Angluin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Eisenstat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonid (Aryeh)","family":"Kontorovich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lev","family":"Reyzin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"18_CR1","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1006\/inco.1998.2664","volume":"141","author":"J.A. Aslam","year":"1998","unstructured":"Aslam, J.A., Decatur, S.E.: General bounds on statistical query learning and PAC learning with noise via hypothesis boosting. Information and Computation\u00a0141(2), 85\u2013118 (1998)","journal-title":"Information and Computation"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1145\/195058.195147","volume-title":"STOC 1994: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing","author":"A. Blum","year":"1994","unstructured":"Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., Rudich, S.: Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In: STOC 1994: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pp. 253\u2013262. ACM, New York (1994)"},{"issue":"1","key":"18_CR3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1006\/inco.1997.2648","volume":"138","author":"Y. Freund","year":"1997","unstructured":"Freund, Y., Kearns, M.J., Ron, D., Rubinfeld, R., Schapire, R.E., Sellie, L.: Efficient learning of typical finite automata from random walks. Information and Computation\u00a0138(1), 23\u201348 (1997)","journal-title":"Information and Computation"},{"issue":"3","key":"18_CR4","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"E. Mark Gold","year":"1978","unstructured":"Mark Gold, E.: Complexity of automaton identification from given data. Information and Control\u00a037(3), 302\u2013320 (1978)","journal-title":"Information and Control"},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-3-540-85363-3_38","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"J. Jackson","year":"2008","unstructured":"Jackson, J., Lee, H., Servedio, R., Wan, A.: Learning random monotone DNF. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 483\u2013497. Springer, Heidelberg (2008)"},{"issue":"5","key":"18_CR6","doi-asserted-by":"publisher","first-page":"1107","DOI":"10.1137\/S0097539704444555","volume":"34","author":"J.C. Jackson","year":"2005","unstructured":"Jackson, J.C., Servedio, R.A.: Learning random log-depth decision trees under the uniform distribution. SIAM J. Comput.\u00a034(5), 1107\u20131128 (2005)","journal-title":"SIAM J. Comput."},{"key":"18_CR7","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1145\/73007.73049","volume-title":"STOC 1989: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing","author":"M. Kearns","year":"1989","unstructured":"Kearns, M., Valiant, L.G.: Crytographic limitations on learning boolean formulae and finite automata. In: STOC 1989: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 433\u2013444. ACM, New York (1989)"},{"issue":"6","key":"18_CR8","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1145\/293347.293351","volume":"45","author":"M. Kearns","year":"1998","unstructured":"Kearns, M.: Efficient noise-tolerant learning from statistical queries. J. ACM\u00a045(6), 983\u20131006 (1998)","journal-title":"J. ACM"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/130385.130390","volume-title":"COLT 1992: Proceedings of the Fifth Annual Workshop on Computational Learning Theory","author":"K.J. Lang","year":"1992","unstructured":"Lang, K.J.: Random DFA\u2019s can be approximately learned from sparse uniform examples. In: COLT 1992: Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pp. 45\u201352. ACM, New York (1992)"},{"issue":"3","key":"18_CR10","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/0022-0000(90)90028-J","volume":"41","author":"L. Pitt","year":"1990","unstructured":"Pitt, L., Warmuth, M.K.: Prediction-preserving reducibility. J. Comput. Syst. Sci.\u00a041(3), 430\u2013467 (1990)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Sellie, L.: Learning random monotone DNF under the uniform distribution. In: COLT, pp. 181\u2013192 (2008)","DOI":"10.1145\/1536414.1536424"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"Sellie, L.: Exact learning of random DNF over the uniform distribution. In: STOC, pp. 45\u201354 (2009)","DOI":"10.1145\/1536414.1536424"},{"key":"18_CR13","volume-title":"Finite Automata: Behavior and Synthesis","author":"B.A. Trakhtenbrot","year":"1973","unstructured":"Trakhtenbrot, B.A., Barzdin, Y.M.: Finite Automata: Behavior and Synthesis. North Holland, Amsterdam (1973)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16108-7_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T22:28:42Z","timestamp":1685744922000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16108-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642161070","9783642161087"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16108-7_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}