{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:42:22Z","timestamp":1787341342425,"version":"build-2736575974"},"reference-count":69,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1536\/14"],"award-info":[{"award-number":["1536\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1420692"],"award-info":[{"award-number":["CCF-1420692"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217423"],"award-info":[{"award-number":["CCF-1217423"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1065125"],"award-info":[{"award-number":["CCF-1065125"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1115703"],"award-info":[{"award-number":["CCF-1115703"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1319788"],"award-info":[{"award-number":["CCF-1319788"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>In many situations, sample data is obtained from a noisy or imperfect source. In order to address such corruptions, this paper introduces the concept of a sampling corrector. Such algorithms use structure that the distribution is purported to have, in order to allow one to make \u201con-the-fly\u201d corrections to samples drawn from probability distributions. These algorithms then act as filters between the noisy data and the end user. We show connections between sampling correctors, distribution learning algorithms, and distribution property testing algorithms. We show that these connections can be utilized to expand the applicability of known distribution learning and property testing algorithms as well as to achieve improved algorithms for those tasks. As a first step, we show how to design sampling correctors using proper learning algorithms. We then focus on the question of whether algorithms for sampling correctors can be more efficient in terms of sample complexity than learning algorithms for the analogous families of distributions. When correcting monotonicity, we show that this is indeed the case when also granted query access to the cumulative distribution function. We also obtain sampling correctors for monotonicity even without this stronger type of access, provided that the distribution be originally very close to monotone (namely, at a distance $O(1\/\\log^2 n)$). In addition to that, we consider a restricted error model that aims at capturing \u201cmissing data\u201d corruptions. In this model, we show that distributions that are close to monotone have sampling correctors that are significantly more efficient than achievable by the learning approach. We consider the question of whether an additional source of independent random bits is required by sampling correctors to implement the correction process. We show that for correcting close-to-uniform distributions and close-to-monotone distributions, no additional source of random bits is required, as the samples from the input source itself can be used to produce this randomness.<\/jats:p>","DOI":"10.1137\/16m1076666","type":"journal-article","created":{"date-parts":[[2018,7,19]],"date-time":"2018-07-19T13:07:02Z","timestamp":1532005622000},"page":"1373-1423","source":"Crossref","is-referenced-by-count":0,"title":["Sampling Correctors"],"prefix":"10.1137","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7153-5211","authenticated-orcid":true,"given":"Cl\u00e9ment L.","family":"Canonne","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Themis","family":"Gouleakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,7,19]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9075-9"},{"key":"atypb2","unstructured":"J. Acharya, I. Diakonikolas, J. Z. Li, and L. Schmidt,\n                      Sample-Optimal Density Estimation in Nearly-Linear Time\n                      ,arXiv:1506.00671[cs.DS], 2015."},{"key":"atypb3","first-page":"1682","author":"Acharya J.","year":"2014","journal-title":"Proceedings of the IEEE International Symposium on Information Theory"},{"key":"atypb4","first-page":"242","volume":"27","author":"Barnett Vic","year":"1978","journal-title":"J. R. Stat. Soc. Ser. C. Appl. Stat."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403645"},{"key":"atypb6","first-page":"169","volume":"65","author":"Balakrishnan S.","year":"2017","journal-title":"Proc. Mach. Learn. Res."},{"key":"atypb7","unstructured":"T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White,\n                      Testing Closeness of Discrete Distributions\n                      ,arXiv:1009.5397[cs.DS], 2010."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/100808186"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176350489"},{"key":"atypb10","first-page":"381","author":"Batu T.","year":"2004","journal-title":"New York"},{"key":"atypb11","first-page":"73","author":"Blum M.","year":"1990","journal-title":"New York"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20182"},{"key":"atypb13","unstructured":"Z. Brakerski,\n                      Local Property Restoring\n                      , manuscript, 2008."},{"key":"atypb14","unstructured":"C. L. Canonne,\n                      A Survey on Distribution Testing: Your Data Is Big. But Is It Blue?\n                      , Technical Report TR15-063,https:\/\/eccc.weizmann.ac.il\/report\/2015\/063\/, 2015."},{"key":"atypb15","first-page":"1","author":"Canonne C. L.","year":"2017","journal-title":"Theory Comput. Syst."},{"key":"atypb16","first-page":"1380","author":"Chan S.-O.","year":"2013","journal-title":"Philadelphia"},{"key":"atypb17","first-page":"604","author":"Chan S.-O.","year":"2014","journal-title":"New York"},{"key":"atypb18","first-page":"1844","volume":"2014","author":"Chan S.-O.","year":"2014","journal-title":"Proceedings of the Annual Conference on Neural Information Processing Systems"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"S. Chakraborty, E. Fischer, Y. Goldhirsh, and A. Matsliah,\n                      On the power of conditional samples in distribution testing\n                      , in Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ACM, New York, 2013., pp. 561-580.","DOI":"10.1145\/2422436.2422497"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"S. Chakraborty, D. Garc\u00eda-Soriano, and A. Matsliah,\n                      Efficient sample extractors for juntas with applications\n                      , in Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, L. Aceto, M. Henzinger, and J. Sgall, eds., Lecture Notes in Comput. Sci. 6755, Springer, New York, 2011, pp. 545-556.","DOI":"10.1007\/978-3-642-22006-7_46"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"A. Campagna, A. Guo, and R. Rubinfeld,\n                      Local reconstructors and tolerant testers for connectivity and diameter\n                      , in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques: 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, P. Raghavendra, S. Raskhodnikova, K. Jansen, J. D. P. Rolim, eds., Lecture Notes in Comput. Sci. 8096, Springer, Berlin, 2013, pp. 411-424.","DOI":"10.1007\/978-3-642-40328-6_29"},{"key":"atypb22","first-page":"93","author":"Canonne C. L.","year":"2016","journal-title":"ACM"},{"key":"atypb23","first-page":"283","author":"Canonne C. L.","year":"2014","journal-title":"Languages and Programming"},{"key":"atypb24","first-page":"1174","author":"Canonne C. L.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb25","first-page":"47","author":"Charikar M.","year":"2017","journal-title":"ACM"},{"key":"atypb26","first-page":"217","author":"Daskalakis C.","year":"2013","journal-title":"Proceedings of the Symposium on Foundations of Computer Science, IEEE"},{"key":"atypb27","first-page":"709","author":"Daskalakis C.","year":"2012","journal-title":"New York"},{"key":"atypb28","first-page":"1833","author":"Daskalakis C.","year":"2013","journal-title":"Philadelphia"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a020"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"P. Diaconis,\n                      Basics of representations and characters\n                      , in Group Representations in Probability and Statistics, Institute of Mathematical Statistics, Hayward, CA, 1988, pp. 5-16.","DOI":"10.1214\/lnms\/1215467411"},{"key":"atypb31","first-page":"1183","author":"Daskalakis C.","year":"2014","journal-title":"Barcelona"},{"key":"atypb32","first-page":"655","author":"Diakonikolas I.","year":"2016","journal-title":"Proceedings of in Symposium on Foundations of Computer Science, IEEE"},{"key":"atypb33","unstructured":"I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart,\n                      Being robust (in high dimensions) can be practical\n                      , in Proc. Mach. 70, Learn. Res. (2017), pp. 999-1008."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.171"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728174"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"L. Devroye and G. Lugosi,\n                      Combinatorial Methods in Density Estimation\n                      , Springer Ser. Statist., Springer, New York, 2001.","DOI":"10.1007\/978-1-4613-0125-7"},{"key":"atypb37","first-page":"1","volume":"39","author":"Dempster A. P.","year":"1977","journal-title":"Ser. B Stat. Math."},{"key":"atypb38","unstructured":"O. Goldreich and D. Ron,\n                      On Testing Expansion in Bounded-Degree Graphs\n                      , Technical Report TR00-020,https:\/\/eccc.weizmann.ac.il\/report\/2000\/020\/, 2000."},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1080\/03461238.1956.10414936"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"D. M Hawkins,\n                      Identification of Outliers\n                      , Springer, Dordrecht, 1980.","DOI":"10.1007\/978-94-015-3994-4"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1111\/2041-210X.12144"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"P. J. Huber and E. M. Ronchetti,\n                      Robust Statistics\n                      , 2nd ed., Wiley Series in Probability and Statistics, John Wiley & Sons, Hoboken, NJ, 2009.","DOI":"10.1002\/9780470434697"},{"key":"atypb43","unstructured":"F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel,\n                      Robust Statistics: The Approach Based on Influence Functions\n                      , John Wiley & Sons, Hoboken, NJ, 2011."},{"key":"atypb44","unstructured":"B. Iglewicz and D. C. Hoaglin,\n                      How to Detect and Handle Outliers\n                      , ASQ Press, Milwaukee, WI, 1993."},{"key":"atypb45","first-page":"15","author":"Indyk P.","year":"2012","journal-title":"New York"},{"key":"atypb46","first-page":"248","author":"Impagliazzo R.","year":"1989","journal-title":"IEEE"},{"key":"atypb47","first-page":"433","author":"Jha M.","year":"2011","journal-title":"Proceedings of the Symposium on Foundations of Computer Science"},{"key":"atypb48","first-page":"273","author":"Kearns M.","year":"1994","journal-title":"New York"},{"key":"atypb49","first-page":"397","author":"Kushilevitz E.","year":"1994","journal-title":"Heidelberg"},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"R. J. A. Little and D. B. Rubin,\n                      Statistical Analysis with Missing Data\n                      , 2nd ed., Wiley Series in Probability and Statistics, John Wiley & Sons, Hoboken, NJ, 2002.","DOI":"10.1002\/9781119013563"},{"key":"atypb51","first-page":"665","author":"Lai K. A.","year":"2016","journal-title":"Proceedings of the Symposium Foundations of Computer Science, IEEE"},{"key":"atypb52","unstructured":"S Maciej,\n                      Anticoncentration of the convolution of two characteristic functions\n                      , MathOverflow,http:\/\/mathoverflow.net\/q\/148973(version: 2013-11-16), 2013."},{"key":"atypb53","unstructured":"S Maciej,\n                      Convergence rate of the convolution of almost uniform measures on $\\mathbb{Z}_p$\n                      , MathOverflow,http:\/\/mathoverflow.net\/q\/148779(version: 2013-11-13), 2013."},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176990746"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.928987"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.4249\/scholarpedia.4258"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197329508"},{"key":"atypb58","doi-asserted-by":"crossref","unstructured":"D. B. Rubin,\n                      Multiple Imputation for Nonresponse in Surveys\n                      , John Wiley & Sons, Hoboken, NJ, 1987.","DOI":"10.1002\/9780470316696"},{"key":"atypb59","doi-asserted-by":"crossref","unstructured":"Joseph L. Schafer,\n                      Analysis of Incomplete Multivariate Data\n                      , CRC Press, Boca Raton, FL, 1997.","DOI":"10.1201\/9781439821862"},{"key":"atypb60","first-page":"291","volume":"190","author":"Signor P. W","year":"1982","journal-title":"Geol. Soc. Amer. Spec. Pap."},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1137\/080728561"},{"key":"atypb62","first-page":"1623","volume":"8","author":"Saar-Tsechansky M.","year":"2007","journal-title":"J. Mach. Learn. Res."},{"key":"atypb63","first-page":"251","author":"Sahai A.","year":"1998","journal-title":"RI"},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1111\/1468-2478.4702006"},{"key":"atypb65","unstructured":"J. W. Tukey,\n                      A Survey of Sampling from Contaminated Distributions\n                      , in Contributions to Probability and Statistics, I. Olkin, ed., Stanford University Press, Stanford, CA, 1960, pp. 448-485."},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"atypb67","unstructured":"P. Valiant, private communication, May 2015."},{"key":"atypb68","first-page":"403","author":"Valiant G.","year":"2011","journal-title":"Proceedings of the Symposium on Foundations of Computer Science"},{"key":"atypb69","doi-asserted-by":"crossref","unstructured":"S. Yekhanin,\n                      Locally Decodable Codes\n                      , Now Publishers, Hanover, MA, 2010.","DOI":"10.1561\/9781601985453"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1076666","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:14:21Z","timestamp":1787339661000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1076666"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":69,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1076666"],"URL":"https:\/\/doi.org\/10.1137\/16m1076666","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}