{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T13:05:08Z","timestamp":1765112708717},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642244117"},{"type":"electronic","value":"9783642244124"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-24412-4_32","type":"book-chapter","created":{"date-parts":[[2011,10,6]],"date-time":"2011-10-06T04:41:17Z","timestamp":1317876077000},"page":"413-424","source":"Crossref","is-referenced-by-count":7,"title":["On Noise-Tolerant Learning of Sparse Parities and Related Problems"],"prefix":"10.1007","author":[{"given":"Elena","family":"Grigorescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lev","family":"Reyzin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Santosh","family":"Vempala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"32_CR1","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.jcss.2007.04.011","volume":"74","author":"M. Alekhnovich","year":"2008","unstructured":"Alekhnovich, M., Braverman, M., Feldman, V., Klivans, A.R., Pitassi, T.: The complexity of properly learning simple concept classes. J. Comput. Syst. Sci.\u00a074(1), 16\u201334 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"Andoni, A., and Indyk, P. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In: FOCS, pp.\u00a0459\u2013468 (2006)","DOI":"10.1109\/FOCS.2006.49"},{"issue":"4","key":"32_CR3","first-page":"343","volume":"2","author":"D. Angluin","year":"1987","unstructured":"Angluin, D., Laird, P.D.: Learning from noisy examples. Machine Learning\u00a02(4), 343\u2013370 (1987)","journal-title":"Machine Learning"},{"issue":"1\/2","key":"32_CR4","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/PL00013833","volume":"22","author":"A. Blum","year":"1998","unstructured":"Blum, A., Frieze, A.M., Kannan, R., Vempala, S.: A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica\u00a022(1\/2), 35\u201352 (1998)","journal-title":"Algorithmica"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"Blum, A., Furst, M.L., Jackson, J.C., Kearns, M.J., Mansour, Y., Rudich, S.: Weakly learning dnf and characterizing statistical query learning using fourier analysis. In: STOC, pp. 253\u2013262 (1994)","DOI":"10.1145\/195058.195147"},{"issue":"4","key":"32_CR6","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.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM\u00a050(4), 506\u2013519 (2003)","journal-title":"J. ACM"},{"issue":"1","key":"32_CR7","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.ipl.2010.10.009","volume":"111","author":"H. Buhrman","year":"2010","unstructured":"Buhrman, H., Garc\u00eda-Soriano, D., Matsliah, A.: Learning parities in the mistake-bound model. Inf. Process. Lett.\u00a0111(1), 16\u201321 (2010)","journal-title":"Inf. Process. Lett."},{"key":"32_CR8","unstructured":"Erickson, J.: Lower bounds for linear satisfiability problems. In: SODA, Philadelphia, PA, USA, pp. 388\u2013395 (1995)"},{"issue":"2","key":"32_CR9","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/070684914","volume":"39","author":"V. Feldman","year":"2009","unstructured":"Feldman, V., Gopalan, P., Khot, S., Ponnuswami, A.K.: On agnostic learning of parities, monomials, and halfspaces. SIAM J. Comput.\u00a039(2), 606\u2013645 (2009)","journal-title":"SIAM J. Comput."},{"key":"32_CR10","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: STOC, pp. 25\u201332 (1989)","DOI":"10.1145\/73007.73010"},{"key":"32_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-45682-1_4","volume-title":"Advances in Cryptology - ASIACRYPT 2001","author":"N.J. Hopper","year":"2001","unstructured":"Hopper, N.J., Blum, M.: Secure human identification protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol.\u00a02248, pp. 52\u201366. Springer, Heidelberg (2001)"},{"key":"32_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1007\/978-3-540-85363-3_38","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"J.C. Jackson","year":"2008","unstructured":"Jackson, J.C., Lee, H.K., Servedio, R.A., 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":"3","key":"32_CR13","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1016\/j.jcss.2004.10.015","volume":"71","author":"A.T. Kalai","year":"2005","unstructured":"Kalai, A.T., Servedio, R.A.: Boosting in the presence of noise. J. Comput. Syst. Sci.\u00a071(3), 266\u2013290 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"32_CR14","doi-asserted-by":"crossref","unstructured":"Katz, J.: Efficient cryptographic protocols based on the hardness of learning parity with noise. In: IMA Int. Conf., pp. 1\u201315 (2007)","DOI":"10.1007\/978-3-540-77272-9_1"},{"key":"32_CR15","doi-asserted-by":"crossref","unstructured":"Kearns, M.J.: Efficient noise-tolerant learning from statistical queries. In: STOC, pp. 392\u2013401 (1993)","DOI":"10.1145\/167088.167200"},{"key":"32_CR16","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-540-27819-1_16","volume-title":"Learning Theory","author":"A.R. Klivans","year":"2004","unstructured":"Klivans, A.R., Servedio, R.A.: Toward attribute efficient learning of decision lists and parities. In: Shawe-Taylor, J., Singer, Y. (eds.) COLT 2004. LNCS (LNAI), vol.\u00a03120, pp. 224\u2013238. Springer, Heidelberg (2004)"},{"issue":"6","key":"32_CR17","doi-asserted-by":"publisher","first-page":"1331","DOI":"10.1137\/0222080","volume":"22","author":"E. Kushilevitz","year":"1993","unstructured":"Kushilevitz, E., Mansour, Y.: Learning decision trees using the fourier spectrum. SIAM J. Comput.\u00a022(6), 1331\u20131348 (1993)","journal-title":"SIAM J. Comput."},{"key":"32_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/11538462_32","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"V. Lyubashevsky","year":"2005","unstructured":"Lyubashevsky, V.: The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 378\u2013389. Springer, Heidelberg (2005)"},{"issue":"3","key":"32_CR19","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1016\/j.jcss.2004.04.002","volume":"69","author":"E. Mossel","year":"2004","unstructured":"Mossel, E., O\u2019Donnell, R., Servedio, R.A.: Learning functions of k relevant variables. J. Comput. Syst. Sci.\u00a069(3), 421\u2013434 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"32_CR20","doi-asserted-by":"crossref","unstructured":"Panigrahy, R., Talwar, K., Wieder, U.: A geometric approach to lower bounds for approximate near-neighbor search and partial match. In: FOCS, pp. 414\u2013423 (2008)","DOI":"10.1109\/FOCS.2008.68"},{"key":"32_CR21","doi-asserted-by":"crossref","unstructured":"Panigrahy, R., Talwar, K., Wieder, U.: Lower bounds on near neighbor search via metric expansion. In: FOCS, pp. 805\u2013814 (2010)","DOI":"10.1109\/FOCS.2010.82"},{"key":"32_CR22","doi-asserted-by":"crossref","unstructured":"Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: STOC, pp. 333\u2013342 (2009)","DOI":"10.1145\/1536414.1536461"},{"key":"32_CR23","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM\u00a056(6) (2009)","DOI":"10.1145\/1568318.1568324"},{"key":"32_CR24","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":"32_CR25","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"},{"issue":"11","key":"32_CR26","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. Commun. ACM\u00a027(11), 1134\u20131142 (1984)","journal-title":"Commun. ACM"},{"key":"32_CR27","doi-asserted-by":"crossref","unstructured":"Verbeurgt, K.A.: Learning dnf under the uniform distribution in quasi-polynomial time. In: COLT, pp. 314\u2013326 (1990)","DOI":"10.1016\/B978-1-55860-146-8.50027-8"}],"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-24412-4_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,10]],"date-time":"2023-06-10T08:21:21Z","timestamp":1686385281000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-24412-4_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642244117","9783642244124"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-24412-4_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}