{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:44:38Z","timestamp":1792111478232,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":32,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_401","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:20Z","timestamp":1461269000000},"page":"2090-2095","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Statistical Query Learning"],"prefix":"10.1007","author":[{"given":"Vitaly","family":"Feldman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"401_CR19784","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1023\/A:1022873112823","volume":"2","author":"D Angluin","year":"1988","unstructured":"Angluin D, Laird P (1988) Learning from noisy examples. Mach Learn 2:343\u2013370","journal-title":"Mach Learn"},{"issue":"2","key":"401_CR19785","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1006\/inco.1998.2664","volume":"141","author":"J Aslam","year":"1998","unstructured":"Aslam J, Decatur S (1998) General bounds on statistical query learning and pac learning with noise via hypothesis boosting. Inf Comput 141(2):85\u2013118","journal-title":"Inf Comput"},{"key":"401_CR19786","first-page":"1295","volume-title":"Statistical active learning algorithms","author":"M-F Balcan","year":"2013","unstructured":"Balcan M-F, Feldman V (2013) Statistical active learning algorithms. In: NIPS, Lake Tahoe, pp\u00a01295\u20131303"},{"key":"401_CR19787","first-page":"232","volume-title":"Learning by distances","author":"S Ben-David","year":"1990","unstructured":"Ben-David S, Itai A, Kushilevitz E (1990) Learning by distances. In: Proceedings of COLT, Rochester, pp\u00a0232\u2013245"},{"key":"401_CR19788","first-page":"128","volume-title":"Practical privacy: the SuLQ framework","author":"A Blum","year":"2005","unstructured":"Blum A, Dwork C, McSherry F, Nissim K (2005) Practical privacy: the SuLQ framework. In: Proceedings of PODS, Baltimore, pp\u00a0128\u2013138"},{"issue":"1\/2","key":"401_CR19789","first-page":"35","volume":"22","author":"A Blum","year":"1997","unstructured":"Blum A, Frieze A, Kannan R, Vempala S (1997) A polynomial time algorithm for learning noisy linear threshold functions. Algorithmica 22(1\/2):35\u201352","journal-title":"Algorithmica"},{"key":"401_CR19790","first-page":"253","volume-title":"Weakly learning DNF and characterizing statistical query learning using Fourier analysis","author":"A Blum","year":"1994","unstructured":"Blum A, Furst M, Jackson J, Kearns M, Mansour Y, Rudich S (1994) Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In: Proceedings of STOC, Montr\u00e9al, pp\u00a0253\u2013262"},{"issue":"4","key":"401_CR19791","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A Blum","year":"2003","unstructured":"Blum A, Kalai A, Wasserman H (2003) Noise-tolerant learning, the parity problem, and the statistical query model. J ACM 50(4):506\u2013519","journal-title":"J ACM"},{"key":"401_CR19792","first-page":"359","volume":"2","author":"N Bshouty","year":"2002","unstructured":"Bshouty N, Feldman V (2002) On using extended statistical queries to avoid membership queries. J Mach Learn Res 2:359\u2013395","journal-title":"J Mach Learn Res"},{"key":"401_CR19793","first-page":"281","volume-title":"Map-reduce for machine learning on multicore","author":"C Chu","year":"2006","unstructured":"Chu C, Kim S, Lin Y, Yu Y, Bradski G, Ng A, Olukotun K (2006) Map-reduce for machine learning on multicore. In: Proceedings of NIPS, Vancouver, pp\u00a0281\u2013288"},{"key":"401_CR19794","doi-asserted-by":"crossref","unstructured":"Dachman-Soled D, Feldman V, Tan L-Y, Wan A, Wimmer K (2014) Approximate resilience, monotonicity, and the complexity of agnostic learning. arXiv, CoRR, abs\/1405.5268","DOI":"10.1137\/1.9781611973730.34"},{"key":"401_CR19795","first-page":"315","volume-title":"A simple polynomial-time rescaling algorithm for solving linear programs","author":"J Dunagan","year":"2004","unstructured":"Dunagan J, Vempala S (2004) A simple polynomial-time rescaling algorithm for solving linear programs. In: Proceedings of STOC, Chicago, pp\u00a0315\u2013320"},{"key":"401_CR19796","first-page":"265","volume-title":"Calibrating noise to sensitivity in private data analysis","author":"C Dwork","year":"2006","unstructured":"Dwork C, McSherry F, Nissim K, Smith A (2006) Calibrating noise to sensitivity in private data analysis. In: TCC, New York, pp\u00a0265\u2013284"},{"key":"401_CR19797","first-page":"619","volume-title":"Evolvability from learning algorithms","author":"V Feldman","year":"2008","unstructured":"Feldman V (2008) Evolvability from learning algorithms. In: Proceedings of STOC, Victoria, pp\u00a0619\u2013628"},{"issue":"5","key":"401_CR19798","doi-asserted-by":"publisher","first-page":"1444","DOI":"10.1016\/j.jcss.2011.12.024","volume":"78","author":"V Feldman","year":"2012","unstructured":"Feldman V (2012) A complete characterization of statistical query learning with applications to evolvability. J Comput Syst Sci 78(5):1444\u20131459","journal-title":"J Comput Syst Sci"},{"key":"401_CR19799","first-page":"1283","volume-title":"Open problem: the statistical query complexity of learning sparse halfspaces","author":"V Feldman","year":"2014","unstructured":"Feldman V (2014) Open problem: the statistical query complexity of learning sparse halfspaces. In: COLT, Barcelona, pp\u00a01283\u20131289"},{"key":"401_CR19800","first-page":"655","volume-title":"Statistical algorithms and a lower bound for planted clique","author":"V Feldman","year":"2013","unstructured":"Feldman V, Grigorescu E, Reyzin L, Vempala S, Xiao Y (2013) Statistical algorithms and a lower bound for planted clique. In: STOC, Palo Alto. ACM, pp\u00a0655\u2013664"},{"key":"401_CR19801","first-page":"1","volume":"16","author":"V Feldman","year":"2012","unstructured":"Feldman V, Kanade V (2012) Computational bounds on statistical query learning. In: COLT, Edinburgh, pp\u00a016.1\u201316.22","journal-title":"COLT, Edinburgh, pp"},{"key":"401_CR19802","first-page":"273","volume":"19","author":"V Feldman","year":"2011","unstructured":"Feldman V, Lee H, Servedio R (2011) Lower bounds and hardness amplification for learning shallow monotone formulas. In: COLT, Budapest, vol\u00a019, pp\u00a0273\u2013292","journal-title":"COLT, Budapest, vol"},{"key":"401_CR19803","unstructured":"Feldman V, Perkins W, Vempala S (2013) On the complexity of random satisfiability problems with planted solutions. In: CoRR, abs\/1311.4821"},{"key":"401_CR19804","first-page":"45","volume-title":"Learning with queries corrupted by classification noise","author":"J Jackson","year":"1997","unstructured":"Jackson J, Shamir E, Shwartzman C (1997) Learning with queries corrupted by classification noise. In: Proceedings of the fifth Israel symposium on the theory of computing systems, Ramat-Gan, pp\u00a045\u201353"},{"key":"401_CR19805","first-page":"437","volume-title":"A close look to margin complexity and related parameters","author":"M Kallweit","year":"2011","unstructured":"Kallweit M, Simon H (2011) A close look to margin complexity and related parameters. In: COLT, Budapest, pp\u00a0437\u2013456"},{"issue":"3","key":"401_CR19806","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1137\/090756090","volume":"40","author":"SP Kasiviswanathan","year":"2011","unstructured":"Kasiviswanathan SP, Lee HK, Nissim K, Raskhodnikova S, Smith A (2011) What can we learn privately? SIAM J Comput 40(3):793\u2013826","journal-title":"SIAM J Comput"},{"issue":"6","key":"401_CR19807","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1145\/293347.293351","volume":"45","author":"M Kearns","year":"1998","unstructured":"Kearns M (1998) Efficient noise-tolerant learning from statistical queries. J ACM 45(6): 983\u20131006","journal-title":"J ACM"},{"issue":"2\u20133","key":"401_CR19808","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10994-007-5010-1","volume":"69","author":"A Klivans","year":"2007","unstructured":"Klivans A, Sherstov A (2007) Unconditional lower bounds for learning intersections of halfspaces. Mach Learn 69(2\u20133):97\u2013114","journal-title":"Mach Learn"},{"key":"401_CR19809","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-1685-5","volume-title":"Learning from good and bad data","author":"P Laird","year":"1988","unstructured":"Laird P (1988) Learning from good and bad data. Kluwer Academic, Boston"},{"issue":"2","key":"401_CR19810","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s00037-008-0242-4","volume":"17","author":"AA Sherstov","year":"2008","unstructured":"Sherstov AA (2008) Halfspace matrices. Comput Complex 17(2):149\u2013178","journal-title":"Comput Complex"},{"key":"401_CR19811","first-page":"393","volume-title":"A characterization of strong learnability in the statistical query model","author":"H Simon","year":"2007","unstructured":"Simon H (2007) A characterization of strong learnability in the statistical query model. In: Proceedings of symposium on theoretical aspects of computer science, Aachen, pp\u00a0393\u2013404"},{"key":"401_CR19812","first-page":"186","volume-title":"Characterizing statistical query learning: simplified notions and proofs","author":"B Sz\u00f6r\u00e9nyi","year":"2009","unstructured":"Sz\u00f6r\u00e9nyi B (2009) Characterizing statistical query learning: simplified notions and proofs. In: Proceedings of ALT, Porto, pp\u00a0186\u2013200"},{"issue":"11","key":"401_CR19813","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant LG (1984) A theory of the learnable. Commun ACM 27(11):1134\u20131142","journal-title":"Commun ACM"},{"key":"401_CR19814","doi-asserted-by":"crossref","unstructured":"Valiant LG (2009) Evolvability. J ACM 56(1):3.1\u20133.21. Earlier version in ECCC, 2006","DOI":"10.1145\/1462153.1462156"},{"issue":"4","key":"401_CR19815","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.10.003","volume":"70","author":"K Yang","year":"2005","unstructured":"Yang K (2005) New lower bounds for statistical query learning. J Comput Syst Sci 70(4):485\u2013509","journal-title":"J Comput Syst Sci"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:53:55Z","timestamp":1792108435000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_401"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_401","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}