{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:20Z","timestamp":1787321120050,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>We consider the problem of testing a basic property of collections of distributions: having similar means. Namely, the algorithm should accept collections of distributions in which all distributions have means that do not differ by more than some given parameter and should reject collections that are relatively far from having this property. By \u201cfar\u201d we mean that it is necessary to modify the distributions in a relatively significant manner (according to some predetermined distance measure) so as to obtain the property. We study this problem in two models. In the first model (the query model) the algorithm may ask for samples from any distribution of its choice, and in the second model (the sampling model) the distributions from which it gets samples are selected randomly. We provide upper and lower bounds in both models. In particular, in the query model, the complexity of the problem is polynomial in $1\/\\epsilon$ (where $\\epsilon$ is the given distance parameter), while in the sampling model, the complexity grows roughly as $m^{1-{\\rm poly}(\\epsilon)}$, where $m$ is the number of distributions.<\/jats:p>","DOI":"10.1137\/120903737","type":"journal-article","created":{"date-parts":[[2014,10,14]],"date-time":"2014-10-14T13:29:23Z","timestamp":1413293363000},"page":"1699-1724","source":"Crossref","is-referenced-by-count":0,"title":["Testing Similar Means"],"prefix":"10.1137","volume":"28","author":[{"given":"Reut","family":"Levi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dana","family":"Ron","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":[[2014,10,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld, and N. Xie,\n                      Testing k-wise and almost k-wise independence\n                      , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), 2007, pp. 496-505.","DOI":"10.1145\/1250790.1250863"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403645"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"T. Batu, L. Fortnow, E. Fischer, R. Kumar, R. Rubinfeld, and P. White,\n                      Testing random variables for independence and identity\n                      , in Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), 2001, pp. 442-451.","DOI":"10.1109\/SFCS.2001.959920"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432626"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"T. Batu, R. Kumar, and R. Rubinfeld,\n                      Sublinear algorithms for testing monotone and unimodal distributions\n                      , in Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), 2004, pp. 381-390.","DOI":"10.1145\/1007352.1007414"},{"key":"atypb6","unstructured":"P. L. Chebyshev,\n                      The\u0301orie des me\u0301canismes connus sous le nom de paralle\u0301logrammes\n                      , Me\u0301moires des Savants e\u0301trangers pre\u0301sente\u0301s a\u0302 l'Acade\u0301mie de Saint-Pe\u0301tersbourg, 7 (1854), pp. 539-586."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176345462"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"atypb9","first-page":"20","volume":"7","author":"Goldreich O.","year":"2000","journal-title":"Electron. Colloq. Comput. Complex."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/1597036.1597038"},{"key":"atypb12","unstructured":"R. J. Larsen and M. L. Marx,\n                      An Introduction to Mathematical Statistics and Its Applications\n                      , Vol. 1, Prentice-Hall, Upper Saddle River, NJ, 2006."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a008"},{"key":"atypb14","unstructured":"W. Mendenhall, R. J. Beaver, and B. M. Beaver,\n                      Introduction to Probability and Statistics\n                      , Brooks\/Cole, Cengage Learning, Boston, MA, 2009."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.928987"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/070701649"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/6.1.1"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"G. Valiant and P. Valiant,\n                      Estimating the unseen: An $n\/\\log(n)$-sample estimator for entropy and support size, shown optimal via new CLTs\n                      , in Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), 2011, pp. 685-694.","DOI":"10.1145\/1993636.1993727"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/080734066"},{"key":"atypb21","first-page":"28","volume":"34","author":"Welch B. L.","year":"1947","journal-title":"Biometrika"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120903737","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:07:35Z","timestamp":1787317655000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120903737"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/120903737"],"URL":"https:\/\/doi.org\/10.1137\/120903737","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}