{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:44:48Z","timestamp":1740123888451,"version":"3.37.3"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T00:00:00Z","timestamp":1575331200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T00:00:00Z","timestamp":1575331200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1350939"],"award-info":[{"award-number":["CCF-1350939"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s10472-019-09675-1","type":"journal-article","created":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T05:14:02Z","timestamp":1575350042000},"page":"759-792","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Learning under p-tampering poisoning attacks"],"prefix":"10.1007","volume":"88","author":[{"given":"Saeed","family":"Mahloujifar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios I.","family":"Diochnos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6839-4697","authenticated-orcid":false,"given":"Mohammad","family":"Mahmoody","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,3]]},"reference":[{"key":"9675_CR1","doi-asserted-by":"crossref","unstructured":"Awasthi, P., Balcan, M.F., Long, P.M.: The power of localization for efficiently learning linear separators with noise. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp 449\u2013458. ACM (2014)","DOI":"10.1145\/2591796.2591839"},{"key":"9675_CR2","doi-asserted-by":"crossref","unstructured":"Austrin, P., Chung, K.-M., Mahmoody, M., Pass, R., Seth, K.: On the impossibility of cryptography with tamperable randomness. In: International Cryptology Conference, pp 462\u2013479. Springer (2014)","DOI":"10.1007\/978-3-662-44371-2_26"},{"issue":"2\u20133","key":"9675_CR3","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1023\/A:1007311411259","volume":"28","author":"D Angluin","year":"1997","unstructured":"Angluin, D., Krikis, M., Sloan, R.H., Tur\u00e1n, G: Malicious omissions and errors in answers to membership queries. Mach. Learn. 28(2\u20133), 211\u2013255 (1997)","journal-title":"Mach. Learn."},{"key":"9675_CR4","doi-asserted-by":"crossref","unstructured":"Aumann, Y., Lindell, Y.: Security against covert adversaries: Efficient protocols for realistic adversaries. Theory Cryptogr., 137\u2013156 (2007)","DOI":"10.1007\/978-3-540-70936-7_8"},{"issue":"4","key":"9675_CR5","first-page":"319","volume":"2","author":"D Angluin","year":"1987","unstructured":"Angluin, D.: Queries and concept learning. Mach. Learn. 2(4), 319\u2013342 (1987)","journal-title":"Mach. Learn."},{"issue":"1","key":"9675_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/15M1027206","volume":"46","author":"S Beigi","year":"2017","unstructured":"Beigi, S., Etesami, O., Gohari, A.: Deterministic randomness extraction from generalized and distributed Santha\u2013Vazirani sources. SIAM J. Comput. 46(1), 1\u201336 (2017)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9675_CR7","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","volume":"24","author":"A Blumer","year":"1987","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Occam\u2019s razor. Inf. Process. Lett. 24(6), 377\u2013380 (1987)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9675_CR8","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Learnability and the Vapnik-Chervonenkis dimension. J. ACM 36(4), 929\u2013965 (1989)","journal-title":"J. ACM"},{"issue":"2","key":"9675_CR9","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0304-3975(01)00403-0","volume":"288","author":"NH Bshouty","year":"2002","unstructured":"Bshouty, N.H., Eiron, N., Kushilevitz, E.: PAC learning with nasty noise. Theor. Comput. Sci. 288(2), 255\u2013275 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9675_CR10","unstructured":"Bentov, I., Gabizon, A., Zuckerman, D.: Bitcoin beacon. arXiv:1605.04559 (2016)"},{"issue":"2","key":"9675_CR11","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/0304-3975(91)90026-X","volume":"86","author":"GM Benedek","year":"1991","unstructured":"Benedek, G.M., Itai, A.: Learnability with respect to fixed distributions. Theor. Comput. Sci. 86(2), 377\u2013390 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"9675_CR12","unstructured":"Biggio, B., Nelson, B., Laskov, P.: Poisoning attacks against support vector machines. In: Proceedings of the 29th International Coference on International Conference on Machine Learning, pp 1467\u20131474. Omnipress (2012)"},{"key":"9675_CR13","doi-asserted-by":"crossref","unstructured":"Barreno, M., Nelson, B., Sears, R., Joseph, A.D., Tygar, J.D.: Can machine learning be secure?. In: Proceedings of the 2006 ACM Symposium on Information, Computer and Communications Security, pp 16\u201325. ACM (2006)","DOI":"10.1145\/1128817.1128824"},{"key":"9675_CR14","doi-asserted-by":"crossref","unstructured":"Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multi-party computation. In: 28th Annual ACM Symposium on Theory of Computing, pp 639\u2013648. ACM Press, Philadephia (1996)","DOI":"10.1145\/237814.238015"},{"key":"9675_CR15","doi-asserted-by":"crossref","unstructured":"Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. In: Proc. 26th FOCS, pp 429\u2013442. IEEE (1985)","DOI":"10.1109\/SFCS.1985.62"},{"issue":"4","key":"9675_CR16","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H Chernoff","year":"1952","unstructured":"Chernoff, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23(4), 493\u2013507 (1952)","journal-title":"Ann. Math. Stat."},{"key":"9675_CR17","doi-asserted-by":"crossref","unstructured":"Charikar, M., Steinhardt, J., Valiant, G.: Learning from untrusted data. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp 47\u201360. ACM (2017)","DOI":"10.1145\/3055399.3055491"},{"key":"9675_CR18","doi-asserted-by":"crossref","unstructured":"Diochnos, D.I.: On the evolution of monotone conjunctions: drilling for best approximations. In: ALT, pp 98\u2013112 (2016)","DOI":"10.1007\/978-3-319-46379-7_7"},{"key":"9675_CR19","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Kamath, G., Kane, D.M., Li, J., Moitra, A, Stewart, A: Robust estimators in high dimensions without the computational intractability. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp 655\u2013664. IEEE (2016)","DOI":"10.1109\/FOCS.2016.85"},{"key":"9675_CR20","unstructured":"Diakonikolas, I, Kamath, G., Kane, D.M., Li, J., Steinhardt, J, Stewart, A: Sever: a robust meta-algorithm for stochastic optimization. arXiv:https:\/\/arxiv.org\/abs\/1803.02815 (2018)"},{"key":"9675_CR21","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Kane, D.M., Stewart, A.: Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp 73\u201384. IEEE (2017)","DOI":"10.1109\/FOCS.2017.16"},{"key":"9675_CR22","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I, Kane, D.M., Stewart, A.: List-decodable robust mean estimation and learning mixtures of spherical Gaussians. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp 1047\u20131060. ACM (2018)","DOI":"10.1145\/3188745.3188758"},{"key":"9675_CR23","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Kong, W., Stewart, A.: Efficient algorithms and lower bounds for robust linear regression. arXiv:1806.00040 (2018)","DOI":"10.1137\/1.9781611975482.170"},{"key":"9675_CR24","unstructured":"Dodis, Y., Ong, S.J., Prabhakaran, M., Sahai, A.: On the (Im)possibility of cryptography with imperfect randomness. In: FOCS IEEE Symposium on Foundations of Computer Science (FOCS) (2004)"},{"key":"9675_CR25","doi-asserted-by":"crossref","unstructured":"Dwork, C., Rothblum, G.N., Vadhan, S.: Boosting and differential privacy. In: 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp 51\u201360. IEEE (2010)","DOI":"10.1109\/FOCS.2010.12"},{"key":"9675_CR26","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Yao, Y.: Privacy with imperfect randomness. In: Annual Cryptology Conference, pp 463\u2013482. Springer (2015)","DOI":"10.1007\/978-3-662-48000-7_23"},{"issue":"3","key":"9675_CR27","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0890-5401(89)90002-3","volume":"82","author":"A Ehrenfeucht","year":"1989","unstructured":"Ehrenfeucht, A., Haussler, D., Kearns, M.J., Valiant, L.G.: A general lower bound on the number of examples needed for learning. Inf. Comput. 82(3), 247\u2013261 (1989)","journal-title":"Inf. Comput."},{"key":"9675_CR28","doi-asserted-by":"crossref","unstructured":"Etesami, O., Mahloujifar, S., Mahmoody, M.: Computational concentration of measure: Optimal bounds, reductions, and more. arXiv:1907.05401. To appear in SODA 2020 (2019)","DOI":"10.1137\/1.9781611975994.21"},{"issue":"2","key":"9675_CR29","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1162\/NECO_a_00697","volume":"27","author":"CR Gonz\u00e1lez","year":"2015","unstructured":"Gonz\u00e1lez, C.R., Abu-Mostafa, Y.S.: Mismatched training and test distributions can outperform matched ones. Neural Comput. 27(2), 365\u2013387 (2015)","journal-title":"Neural Comput."},{"key":"9675_CR30","unstructured":"Garg, S., Jha, S., Mahloujifar, S., Mahmoody, M.: Adversarially robust learning could leverage computational hardness. arXiv:1905.11564(2019)"},{"key":"9675_CR31","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Park, S.: Adaptively secure coin-flipping, revisited (2015)","DOI":"10.1007\/978-3-662-47666-6_53"},{"key":"9675_CR32","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Park, S.: Adaptively secure coin-flipping, revisited. In: International Colloquium on Automata, Languages, and Programming, pp 663\u2013674. Springer (2015)","DOI":"10.1007\/978-3-662-47666-6_53"},{"key":"9675_CR33","unstructured":"Haitner, I., Ishai, Y., Kushilevitz, E., Lindell, Y., Petrank, E.: Black-box constructions of protocols for secure computation. Cryptology ePrint Archive, Report 2010\/164 http:\/\/eprint.iacr.org\/2010\/164 (2010)"},{"issue":"301","key":"9675_CR34","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"issue":"4","key":"9675_CR35","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1137\/0222052","volume":"22","author":"MJ Kearns","year":"1993","unstructured":"Kearns, M.J., Li, M.: Learning in the presence of malicious errors. SIAM J. Comput. 22(4), 807\u2013837 (1993)","journal-title":"SIAM J. Comput."},{"key":"9675_CR36","doi-asserted-by":"crossref","unstructured":"Lai, K.A., Rao, A.B., Vempala, S.: Agnostic estimation of mean and covariance. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp 665\u2013674. IEEE (2016)","DOI":"10.1109\/FOCS.2016.76"},{"key":"9675_CR37","doi-asserted-by":"crossref","unstructured":"Mahloujifar, S., Mahmoody, M.: Blockwise p-tampering attacks on cryptographic primitives, extractors, and learners. In: Theory of Cryptography Conference, pp 245\u2013279. Springer (2017)","DOI":"10.1007\/978-3-319-70503-3_8"},{"key":"9675_CR38","doi-asserted-by":"crossref","unstructured":"Mahloujifar, S, Mahmoody, M: Blockwise p-tampering attacks on cryptographic primitives, extractors, and learners. Cryptology ePrint Archive, Report 2017\/950 https:\/\/eprint.iacr.org\/2017\/950 (2017)","DOI":"10.1007\/978-3-319-70503-3_8"},{"key":"9675_CR39","unstructured":"Mahloujifar, S., Mahmoody, M.: Can adversarially robust learning leveragecomputational hardness? In: Algorithmic Learning Theory, pp. 581\u2013609 (2019)"},{"key":"9675_CR40","unstructured":"Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (2008)"},{"key":"9675_CR41","unstructured":"Papernot, N., McDaniel, P., Sinha, A., Wellman, M.: Towards the science of security and privacy in machine learning. arXiv:1611.03814 (2016)"},{"key":"9675_CR42","unstructured":"Prasad, A., Suggala, A.S., Balakrishnan, S., Ravikumar, P.: Robust estimation via robust gradient estimation. arXiv:1802.06485 (2018)"},{"issue":"4","key":"9675_CR43","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L Pitt","year":"1988","unstructured":"Pitt, L., Valiant, L.G.: Computational limitations on learning from examples. J. ACM 35(4), 965\u2013984 (1988)","journal-title":"J. ACM"},{"key":"9675_CR44","doi-asserted-by":"crossref","unstructured":"Rao, C.R.: Information and the accuracy attainable in the estimation of statistical parameters. In: Breakthroughs in Statistics, pp 235\u2013247. Springer (1992)","DOI":"10.1007\/978-1-4612-0919-5_16"},{"key":"9675_CR45","doi-asserted-by":"crossref","unstructured":"Rubinstein, B.I.P., Nelson, B., Huang, L., Joseph, A.D., Lau, S.-h., Rao, S., Taft, N., Tygar, J.D.: Antidote: understanding and defending against poisoning of anomaly detectors. In: Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement Conference, pp 1\u201314. ACM (2009)","DOI":"10.1145\/1644893.1644895"},{"issue":"2","key":"9675_CR46","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1145\/1639562.1639592","volume":"37","author":"BIP Rubinstein","year":"2009","unstructured":"Rubinstein, B.I.P., Nelson, B., Huang, L., Joseph, A.D., Lau, S -h, Rao, S., Taft, N., Tygar, J.D.: Stealthy poisoning attacks on pca-based anomaly detectors. ACM SIGMETRICS Perform. Eval. Rev. 37(2), 73\u201374 (2009)","journal-title":"ACM SIGMETRICS Perform. Eval. Rev."},{"key":"9675_CR47","unstructured":"Reingold, O., Vadhan, S, Wigderson, A: A note on extracting randomness from Santha-Vazirani sources. Unpublished manuscript (2004)"},{"key":"9675_CR48","unstructured":"Shafahi, A., Huang, W.R., Najibi, M., Suciu, O., Studer, C., Dumitras, T., Goldstein, T.: Poison frogs! targeted clean-label poisoning attacks on neural networks. In: Advances in Neural Information Processing Systems, pp 6103\u20136113 (2018)"},{"issue":"3","key":"9675_CR49","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(95)00016-6","volume":"54","author":"RH Sloan","year":"1995","unstructured":"Sloan, R.H.: Four types of noise in data for PAC learning. Inf. Process. Lett. 54 (3), 157\u2013162 (1995)","journal-title":"Inf. Process. Lett."},{"key":"9675_CR50","unstructured":"Shen, S., Tople, S., Saxena, P.: A uror: Defending against poisoning attacks in collaborative deep learning systems. In: Proceedings of the 32nd Annual Conference on Computer Security Applications, pp 508\u2013519. ACM (2016)"},{"issue":"1","key":"9675_CR51","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0022-0000(86)90044-9","volume":"33","author":"M Santha","year":"1986","unstructured":"Santha, M., Vazirani, U.V.: Generating quasi-random sequences from semi-random sources. J. Comput. Syst. Sci. 33(1), 75\u201387 (1986)","journal-title":"J. Comput. Syst. Sci."},{"issue":"11","key":"9675_CR52","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant, L.G.: A Theory of the Learnable. Commun. ACM 27(11), 1134\u20131142 (1984)","journal-title":"Commun. ACM"},{"key":"9675_CR53","unstructured":"Valiant, L.G.: Learning disjunctions of conjunctions. In: IJCAI, pp 560\u2013566 (1985)"},{"key":"9675_CR54","first-page":"36","volume":"12","author":"J Von Neumann","year":"1951","unstructured":"Von Neumann, J.: 13 various techniques used in connection with random digits. Appl. Math. Ser 12, 36\u201338 (1951)","journal-title":"Appl. Math. Ser"},{"key":"9675_CR55","unstructured":"Wang, Y., Chaudhuri, K.: Data poisoning attacks against online learning. arXiv:1808.08994 (2018)"},{"key":"9675_CR56","unstructured":"Xiao, H., Biggio, B., Brown, G., Fumera, G., Eckert, C., Roli, F.: Is feature selection secure against training data poisoning? In: ICML, pp. 1689\u20131698 (2015)"},{"issue":"3","key":"9675_CR57","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s10994-011-5268-1","volume":"86","author":"H Xu","year":"2012","unstructured":"Xu, H., Mannor, S.: Robustness and generalization. Mach. Learn. 86(3), 391\u2013423 (2012)","journal-title":"Mach. Learn."},{"key":"9675_CR58","doi-asserted-by":"crossref","unstructured":"Yamazaki, K, Kawanabe, M., Watanabe, S., Sugiyama, M, M\u00fcller, K.-R.: Asymptotic Bayesian generalization error when training and test distributions are different. In: ICML, pp 1079\u20131086 (2007)","DOI":"10.1145\/1273496.1273632"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-019-09675-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-019-09675-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-019-09675-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,7]],"date-time":"2022-10-07T13:10:12Z","timestamp":1665148212000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-019-09675-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,3]]},"references-count":58,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["9675"],"URL":"https:\/\/doi.org\/10.1007\/s10472-019-09675-1","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[2019,12,3]]},"assertion":[{"value":"3 December 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}