{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T12:53:01Z","timestamp":1772801581196,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540428756","type":"print"},{"value":"9783540455837","type":"electronic"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45583-3_7","type":"book-chapter","created":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T08:37:04Z","timestamp":1192783024000},"page":"59-76","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["On Learning Correlated Boolean Functions Using Statistical Queries (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Ke","family":"Yang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,10,31]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Andris Ambainis. Quantum lower bounds by quantum arguments, In Proceedings of the 32nd ACM Symposium on Theory of Computing, pages 636\u2013643, 2000.","DOI":"10.1145\/335305.335394"},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1006\/inco.1998.2664","volume":"141","author":"J. Aslam","year":"1998","unstructured":"Javed Aslam and Scott Decatur. General Bounds on Statistical Query Learning and PAC learning with Noise via Hypothesis Boosting, In Information and Computation, 141, pages 85\u2013118 (1998).","journal-title":"Information and Computation"},{"key":"7_CR3","unstructured":"Leemon Baird. Blind Computation. Manuscript, 2001."},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 253\u2013262, 1994.","DOI":"10.1145\/195058.195147"},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/PL00013833","volume":"22","author":"A. Blum","year":"1998","unstructured":"Avrim Blum, Alan Frieze, Ravi Kannan, and Santosh Vempala, A Polynomial-time Algorithm for Learning Noisy Linear Threshold Functions, In Algorithmica, 22:35\u201352, 1998. An extended abstract appears in Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS\u201996), pages 330-338.","journal-title":"Algorithmica"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Avrim Blum, Adam Kalai and Hal Wasserman, Noise-tolerant Learning, the Parity problem, and the Statistical Query model. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 435\u2013440, 2000.","DOI":"10.1145\/335305.335355"},{"key":"7_CR7","unstructured":"Scott Decatur, Efficient Learning from Faulty Data. Ph.D. Thesis, Harvard University, TR-30-95, 1995."},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Oded Goldreich and Leonid Levin, A hard-core predicate for all one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 25\u201332, 1989.","DOI":"10.1145\/73007.73010"},{"key":"7_CR9","unstructured":"Jeff Jackson On the Efficiency of Noise-Tolerant PAC Algorithms Derived from Statistical Queries. In Proceedings of the 13th Annual Workshop on Computational Learning Theory, 2000."},{"issue":"6","key":"7_CR10","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1145\/293347.293351","volume":"45","author":"M. Kearns","year":"1998","unstructured":"Michael Kearns. Efficient noise-tolerant learning from statistical queries. In Journal of the ACM, 45(6), pp. 983\u20131006, 1998. Preliminary version in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pp. 392-401, 1993.","journal-title":"Journal of the ACM"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1006\/jcss.1996.0017","volume":"52","author":"R. Schapire","year":"1996","unstructured":"Robert Schapire and Linda Selle, Learning Sparse Multivariate Polynomials over a Field with Queries and Counterexamples. In Journal of Computer and System Sciences, 52, 201\u2013213, 1996.","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR13","unstructured":"Salil Vadhan, Private Communication."},{"issue":"11","key":"7_CR14","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. Valiant","year":"1984","unstructured":"Leslie Valiant, A theory of the Leanable. In Communications of the ACM, 27(11): 1134\u20131142, November 1984.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45583-3_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,30]],"date-time":"2020-03-30T21:18:21Z","timestamp":1585603101000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45583-3_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540428756","9783540455837"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-45583-3_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"31 October 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}