{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T17:15:30Z","timestamp":1772730930826,"version":"3.50.1"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,2,1]],"date-time":"2013-02-01T00:00:00Z","timestamp":1359676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,2]]},"abstract":"<jats:p>\n            Given samples from two distributions over an\n            <jats:italic>n<\/jats:italic>\n            -element set, we wish to test whether these distributions are statistically close. We present an algorithm which uses sublinear in\n            <jats:italic>n<\/jats:italic>\n            , specifically,\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            <jats:italic>\u03b5<\/jats:italic>\n            <jats:sup>\u22128\/3<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ), independent samples from each distribution, runs in time linear in the sample size, makes no assumptions about the structure of the distributions, and distinguishes the cases when the distance between the distributions is small (less than {\n            <jats:italic>\u03b5<\/jats:italic>\n            <jats:sup>4\/3<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u22121\/3<\/jats:sup>\n            \/32,\n            <jats:italic>\u03b5n<\/jats:italic>\n            <jats:sup>\u22121\/2<\/jats:sup>\n            \/4}) or large (more than\n            <jats:italic>\u03b5<\/jats:italic>\n            ) in \u2113\n            <jats:sub>1<\/jats:sub>\n            distance. This result can be compared to the lower bound of\n            <jats:italic>\u03a9<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            <jats:italic>\u03b5<\/jats:italic>\n            <jats:sup>\u22122\/3<\/jats:sup>\n            ) for this problem given by Valiant [2008].\n          <\/jats:p>\n          <jats:p>Our algorithm has applications to the problem of testing whether a given Markov process is rapidly mixing. We present sublinear algorithms for several variants of this problem as well.<\/jats:p>","DOI":"10.1145\/2432622.2432626","type":"journal-article","created":{"date-parts":[[2013,3,5]],"date-time":"2013-03-05T20:28:36Z","timestamp":1362515316000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":64,"title":["Testing Closeness of Discrete Distributions"],"prefix":"10.1145","volume":"60","author":[{"given":"Tu\u011fkan","family":"Batu","sequence":"first","affiliation":[{"name":"London School of Economics and Political Science"}]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[{"name":"Northwestern University"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology and Tel Aviv University"}]},{"given":"Warren D.","family":"Smith","sequence":"additional","affiliation":[{"name":"Center for Range Voting"}]},{"given":"Patrick","family":"White","sequence":"additional","affiliation":[]}],"member":"320","published-online":{"date-parts":[[2013,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of 21st ACM-SIAM Symposium on Discrete Algorithms. 56--65","author":"Adamaszek M.","unstructured":"Adamaszek , M. , Czumaj , A. , and Sohler , C . 2010. Testing monotone continuous distributions on high-dimensional real cubes . In Proceedings of 21st ACM-SIAM Symposium on Discrete Algorithms. 56--65 . Adamaszek, M., Czumaj, A., and Sohler, C. 2010. Testing monotone continuous distributions on high-dimensional real cubes. In Proceedings of 21st ACM-SIAM Symposium on Discrete Algorithms. 56--65."},{"key":"e_1_2_1_2_1","unstructured":"Aho A. V. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley.   Aho A. V. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms . Addison-Wesley."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, 656--666","author":"Alon N.","unstructured":"Alon , N. , Krivelevich , M. , Fischer , E. , and Szegedy , M . 1999a. Efficient testing of large graphs . In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, 656--666 . Alon, N., Krivelevich, M., Fischer, E., and Szegedy, M. 1999a. Efficient testing of large graphs. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, 656--666."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250863"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380810"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society. 259--269","author":"Batu T.","unstructured":"Batu , T. , Fortnow , L. , Rubinfeld , R. , Smith , W. D. , and White , P . 2000. Testing that distributions are close . In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society. 259--269 . Batu, T., Fortnow, L., Rubinfeld, R., Smith, W. D., and White, P. 2000. Testing that distributions are close. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society. 259--269."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of 42nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE.","author":"Batu T.","unstructured":"Batu , T. , Fortnow , L. , Fischer , E. , Kumar , R. , Rubinfeld , R. , and White , P . 2001. Testing random variables for independence and identity . In Proceedings of 42nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. Batu, T., Fortnow, L., Fischer, E., Kumar, R., Rubinfeld, R., and White, P. 2001. Testing random variables for independence and identity. In Proceedings of 42nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007414"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403645"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_16"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of SODA, SIAM, 366--375","author":"Brautbar M.","unstructured":"Brautbar , M. and Samorodnitsky , A . 2007. Approximating entropy from sublinear samples . In Proceedings of SODA, SIAM, 366--375 . Brautbar, M. and Samorodnitsky, A. 2007. Approximating entropy from sublinear samples. In Proceedings of SODA, SIAM, 366--375."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806728"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806729"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1690"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_15"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798604"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of Innovations in Computer Science.","author":"Chien S.","year":"2010","unstructured":"Chien , S. , Ligett , K. , and McGregor , A. 2010 . Space-efficient estimation of robust statistics and distribution testing . In Proceedings of Innovations in Computer Science. Chien, S., Ligett, K., and McGregor, A. 2010. Space-efficient estimation of robust statistics and distribution testing. In Proceedings of Innovations in Computer Science."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Cover T. M. and Thomas J. A. 1991. Elements of Information Theory. Wiley Series in Telecommunications.   Cover T. M. and Thomas J. A. 1991. Elements of Information Theory . Wiley Series in Telecommunications.","DOI":"10.1002\/0471200611"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614105"},{"key":"e_1_2_1_22_1","unstructured":"Csisz\u00e1r I. 1967. Information-type measures of difference of probability distributions and indirect observations. Studia Scientiarum Mathematicarum Hungarica.  Csisz\u00e1r I. 1967. Information-type measures of difference of probability distributions and indirect observations. Studia Scientiarum Mathematicarum Hungarica ."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.69"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS). 40","author":"Feigenbaum J.","unstructured":"Feigenbaum , J. , Kannan , S. , Strauss , M. , and Viswanathan , M . 1999. An approximate L1-difference algorithm for massive data streams (extended abstract) . In Proceedings of the Symposium on Foundations of Computer Science (FOCS). 40 . Feigenbaum, J., Kannan, S., Strauss, M., and Viswanathan, M. 1999. An approximate L1-difference algorithm for massive data streams (extended abstract). In Proceedings of the Symposium on Foundations of Computer Science (FOCS). 40."},{"key":"e_1_2_1_25_1","volume-title":"An Introduction to Probability Theory and Applications","author":"Feller W.","unstructured":"Feller , W. 1968. An Introduction to Probability Theory and Applications . Vol. 1 . Wiley , New York . Feller, W. 1968. An Introduction to Probability Theory and Applications. Vol. 1. Wiley, New York."},{"key":"e_1_2_1_26_1","first-page":"97","article-title":"The art of uninformed decisions","volume":"75","author":"Fischer E.","year":"2001","unstructured":"Fischer , E. 2001 . The art of uninformed decisions . Bulletin of the EATCS 75 , 97 . Fischer, E. 2001. The art of uninformed decisions. Bulletin of the EATCS 75, 97.","journal-title":"Bulletin of the EATCS"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science.","author":"Fong J.","unstructured":"Fong , J. and Strauss , M . 2000. An approximate Lp-difference algorithm for massive data streams . In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science. Fong, J. and Strauss, M. 2000. An approximate Lp-difference algorithm for massive data streams. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Frieze A. and Kannan R. 1999. Quick approximation to matrices and applications. Combinatorica 19.  Frieze A. and Kannan R. 1999. Quick approximation to matrices and applications. Combinatorica 19 .","DOI":"10.1007\/s004930050052"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of SODA 10","author":"Gibbons P. B.","unstructured":"Gibbons , P. B. and Matias , Y . 1999. Synopsis data structures for massive data sets . In Proceedings of SODA 10 . ACM-SIAM, 909--910. Gibbons, P. B. and Matias, Y. 1999. Synopsis data structures for massive data sets. In Proceedings of SODA 10. ACM-SIAM, 909--910."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_31_1","volume-title":"Tech. Rep. TR00-020, Electronic Colloquium on Computational Complexity.","author":"Goldreich O.","year":"2000","unstructured":"Goldreich , O. and Ron , D . 2000 . On testing expansion in bounded-degree graphs. Tech. Rep. TR00-020, Electronic Colloquium on Computational Complexity. Goldreich, O. and Ron, D. 2000. On testing expansion in bounded-degree graphs. Tech. Rep. TR00-020, Electronic Colloquium on Computational Complexity."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"e_1_2_1_34_1","volume-title":"Matrix Computations","author":"Golub G. H.","unstructured":"Golub , G. H. and van Loan , C. F. 1996. Matrix Computations . The John Hopkins University Press , Baltimore, MD . Golub, G. H. and van Loan, C. F. 1996. Matrix Computations. The John Hopkins University Press, Baltimore, MD."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-008-5054-x"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1597036.1597038"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"Indyk P.","year":"2008","unstructured":"Indyk , P. and McGregor , A. 2008 . Declaring independence via the sketching of sketches . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008). 737--745. Indyk, P. and McGregor, A. 2008. Declaring independence via the sketching of sketches. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008). 737--745."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_43"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365726"},{"key":"e_1_2_1_40_1","series-title":"Lecture Notes in Computer Science","volume-title":"-C","author":"Kannan S.","year":"1991","unstructured":"Kannan , S. and Yao , A. C . -C . 1991 . Program checkers for probability generation. In Proceedings of ICALP 18, Lecture Notes in Computer Science , vol. 510 . Springer-Verlag , 163--173. Kannan, S. and Yao, A. C.-C. 1991. Program checkers for probability generation. In Proceedings of ICALP 18, Lecture Notes in Computer Science, vol. 510. Springer-Verlag, 163--173."},{"key":"e_1_2_1_41_1","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1973. The Art of Computer Programming, Volume III: Sorting and Searching . Addison-Wesley . Knuth, D. E. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley."},{"key":"e_1_2_1_42_1","volume-title":"Testing Statistical Hypotheses","author":"Lehmann E. L.","unstructured":"Lehmann , E. L. 1986. Testing Statistical Hypotheses 2 nd Ed. Wadsworth and Brooks\/Cole , Pacific Grove, CA . Lehmann, E. L. 1986. Testing Statistical Hypotheses 2nd Ed. Wadsworth and Brooks\/Cole, Pacific Grove, CA.","edition":"2"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of Innovations in Computer Science (ICS).","author":"Levi R.","unstructured":"Levi , R. , Ron , D. , and Rubinfeld , R . 2011. Testing properties of collections of distributions . In Proceedings of Innovations in Computer Science (ICS). Levi, R., Ron, D., and Rubinfeld, R. 2011. Testing properties of collections of distributions. In Proceedings of Innovations in Computer Science (ICS)."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01013169"},{"key":"e_1_2_1_45_1","first-page":"118","article-title":"Testing the expansion of a graph","volume":"14","author":"Nachmias A.","year":"2007","unstructured":"Nachmias , A. and Shapira , A. 2007 . Testing the expansion of a graph . Elect. Colloq. Comput. Complex. (ECCC) 14 , 118 . Nachmias, A. and Shapira, A. 2007. Testing the expansion of a graph. Elect. Colloq. Comput. Complex. (ECCC) 14, 118.","journal-title":"Elect. Colloq. Comput. Complex. (ECCC)"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.1933.0009"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.928987"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/280490"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/070701649"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0013-1_15"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v34:1"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Rubinfeld R.\n     and \n      Xie N\n  . \n  2010\n  . Testing non-uniform k-wise independent distributions over product spaces. In Proceedings of ICALP 1 Lecture Notes in Computer Science vol. \n  6198\n  . \n  Springer 565--581.   Rubinfeld R. and Xie N. 2010. Testing non-uniform k -wise independent distributions over product spaces. In Proceedings of ICALP 1 Lecture Notes in Computer Science vol. 6198. Springer 565--581.","DOI":"10.1007\/978-3-642-14165-2_48"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 38th Annual Symposium on the Foundations of Computer Science. IEEE, 448--457","author":"Sahai A.","unstructured":"Sahai , A. and Vadhan , S . 1997. A complete promise problem for statistical zero-knowledge . In Proceedings of the 38th Annual Symposium on the Foundations of Computer Science. IEEE, 448--457 . Sahai, A. and Vadhan, S. 1997. A complete promise problem for statistical zero-knowledge. In Proceedings of the 38th Annual Symposium on the Foundations of Computer Science. IEEE, 448--457."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374432"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022870506888"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2432622.2432626","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2432622.2432626","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:20Z","timestamp":1750234700000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2432622.2432626"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["10.1145\/2432622.2432626"],"URL":"https:\/\/doi.org\/10.1145\/2432622.2432626","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,2]]},"assertion":[{"value":"2010-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}