{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:54:16Z","timestamp":1781078056465,"version":"3.54.1"},"reference-count":89,"publisher":"Emerald","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,11,22]]},"abstract":"<jats:p>We focus on some specific problems in distribution testing, taking goodness-of-fit as a running example. In particular, we do not aim to provide a comprehensive summary of all the topics in the area; but will provide self-contained proofs and derivations of the main results, trying to highlight the unifying techniques.<\/jats:p>","DOI":"10.1561\/0100000114","type":"journal-article","created":{"date-parts":[[2022,11,22]],"date-time":"2022-11-22T09:03:32Z","timestamp":1669107812000},"page":"1032-1198","source":"Crossref","is-referenced-by-count":20,"title":["Topics and Techniques in Distribution Testing: A Biased but Representative Sample"],"prefix":"10.1108","volume":"19","author":[{"given":"Cl\u00e9ment L.","family":"Canonne","sequence":"first","affiliation":[{"name":"University of Sydney ,","place":["Australia"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"140","published-online":{"date-parts":[[2022,11,22]]},"reference":[{"key":"2026032712183032800_ref001","article-title":"Domain compression and its application to randomness-optimal distributed goodness-of-fit","author":"Acharya","journal-title":"Proceedings of Thirty Third Conference on Learning Theory"},{"issue":"1","key":"2026032712183032800_ref002","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1109\/JSAIT.2021.3053569","article-title":"Inference under information constraints III: local privacy constraints","volume":"2","author":"Acharya","year":"2021","journal-title":"IEEE J. Sel. Areas Inf. Theory"},{"issue":"1","key":"2026032712183032800_ref003","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1109\/TIT.2021.3123905","article-title":"Interactive inference under information constraints","volume":"68","author":"Acharya","year":"2022","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2026032712183032800_ref004","article-title":"Optimal rates for nonparametric density estimation under communication constraints","author":"Acharya","journal-title":"Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual"},{"key":"2026032712183032800_ref005","article-title":"Unified lower bounds for interactive high-dimensional estimation under information constraints","author":"Acharya","journal-title":"CoRR"},{"issue":"12","key":"2026032712183032800_ref006","doi-asserted-by":"publisher","first-page":"7835","DOI":"10.1109\/TIT.2020.3028440","article-title":"Inference under information constraints I: Lower bounds from chi-square contraction","volume":"66","author":"Acharya","year":"2020","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"12","key":"2026032712183032800_ref007","doi-asserted-by":"publisher","first-page":"7856","DOI":"10.1109\/TIT.2020.3028439","article-title":"Inference under information constraints II: Communication constraints and shared randomness","volume":"66","author":"Acharya","year":"2020","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2026032712183032800_ref008","article-title":"Optimal Testing for Properties of Distributions","author":"Acharya","journal-title":"Advances in Neural Information Processing Systems 28"},{"key":"2026032712183032800_ref009","first-page":"6879","article-title":"Differentially private testing of identity and closeness of discrete distributions","author":"Acharya","year":"2018","journal-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montr\u00e9al, Canada"},{"key":"2026032712183032800_ref010","article-title":"Hadamard response: Estimating distributions privately, efficiently, and with little communication","author":"Acharya","journal-title":"Proceedings of Machine Learning Research"},{"key":"2026032712183032800_ref011","article-title":"Differentially private identity and equivalence testing of discrete distributions","author":"Aliakbarpour","journal-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10-15, 2018"},{"key":"2026032712183032800_ref012","article-title":"Pan-private uniformity testing","author":"Amin","journal-title":"Proceedings of Thirty Third Conference on Learning Theory"},{"key":"2026032712183032800_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-7379-1","volume":"43","author":"Arnold","journal-title":"Majorization and the Lorenz order: a brief introduction"},{"key":"2026032712183032800_ref014","doi-asserted-by":"publisher","article-title":"Hypothesis testing for highdimensional multinomials: A selective review","author":"Balakrishnan","DOI":"10.1214\/18-AOAS1155SF"},{"key":"2026032712183032800_ref015","first-page":"2384","article-title":"Connecting robust shuffle privacy and pan-privacy","author":"Balcer","year":"2021","journal-title":"SODA"},{"key":"2026032712183032800_ref016","article-title":"Lower bounds for learning distributions under communication constraints via Fisher information","author":"Barnes"},{"key":"2026032712183032800_ref017","article-title":"Generalized uniformity testing","author":"Batu","journal-title":"58th Annual IEEE Symposium on Foundations of Computer Science\u2014FOCS 2017"},{"key":"2026032712183032800_ref018","first-page":"442","article-title":"Testing random variables for independence and identity","author":"Batu","year":"2001","journal-title":"42nd Annual Symposium on Foundations of Computer Science, FOCS 2001"},{"key":"2026032712183032800_ref019","first-page":"189","article-title":"Testing that distributions are close","author":"Batu","year":"2000","journal-title":"41st Annual Symposium on Foundations of Computer Science, FOCS 2000"},{"key":"2026032712183032800_ref020","article-title":"Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms","author":"Berrett","year":"2020","journal-title":"NeurIPS"},{"issue":"3","key":"2026032712183032800_ref021","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1214\/aos\/1176350489","article-title":"On the risk of histograms for estimating decreasing densities","volume":"15","author":"Birg\u00e9","year":"1987","journal-title":"The Annals of Statistics"},{"issue":"2","key":"2026032712183032800_ref022","doi-asserted-by":"publisher","DOI":"10.1145\/3305270","article-title":"Distribution testing lower bounds via reductions from communication complexity","volume":"11","author":"Blais","year":"2019","journal-title":"ACM Trans. Comput. Theory"},{"key":"2026032712183032800_ref023","doi-asserted-by":"publisher","author":"Boucheron","journal-title":"Concentration inequalities","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"2026032712183032800_ref024","first-page":"1011","article-title":"Communication lower bounds for statistical estimation problems via a distributed data processing inequality","author":"Braverman","year":"2016","journal-title":"Symposium on Theory of Computing Conference, STOC\u201916"},{"key":"2026032712183032800_ref025","article-title":"Estimation des densit\u00e9s: Risque minimax","author":"Bretagnolle","journal-title":"S\u00e9minaire de Probabilit\u00e9s, XII (Univ. Strasbourg, Strasbourg, 1976\/1977)"},{"issue":"3","key":"2026032712183032800_ref026","doi-asserted-by":"publisher","first-page":"1727","DOI":"10.3150\/19-BEJ1165","article-title":"Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids","volume":"26","author":"Butucea","year":"2020","journal-title":"Bernoulli"},{"key":"2026032712183032800_ref027","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2016.25","article-title":"Testing Shape Restrictions of Discrete Distributions","author":"Canonne","year":"2016","journal-title":"Proceedings of STACS"},{"key":"2026032712183032800_ref028","author":"Canonne","year":"2020","journal-title":"A short note on learning discrete distributions"},{"key":"2026032712183032800_ref029","doi-asserted-by":"publisher","author":"Canonne","DOI":"10.4086\/toc.gs.2020.009"},{"key":"2026032712183032800_ref030","author":"Canonne","year":"2022","journal-title":"A short note on an inequality between KL and TV"},{"key":"2026032712183032800_ref031","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00224-017-9785-6","article-title":"Testing shape restrictions of discrete distributions","author":"Canonne","year":"2017","journal-title":"Theory of Computing Systems"},{"key":"2026032712183032800_ref032","article-title":"The price of tolerance in distribution testing","author":"Canonne","journal-title":"Conference on Learning Theory, 2-5 July 2022, London, UK"},{"key":"2026032712183032800_ref033","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611977066.13","article-title":"Uniformity testing in the shuffle model: Simpler, better, faster","author":"Canonne","year":"2022","journal-title":"SIAM Symposium on Simplicity in Algorithms (SOSA)"},{"issue":"3","key":"2026032712183032800_ref034","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/130945508","article-title":"Testing probability distributions using conditional samples","volume":"44","author":"Canonne","year":"2015","journal-title":"SIAM Journal on Computing"},{"key":"2026032712183032800_ref035","article-title":"Testing probability distributions underlying aggregated data","author":"Canonne","journal-title":"Proceedings of ICALP"},{"key":"2026032712183032800_ref036","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422497","article-title":"On the power of conditional samples in distribution testing","author":"Chakraborty","year":"2013","journal-title":"Proceedings of ITCS"},{"key":"2026032712183032800_ref037","first-page":"1193","article-title":"Optimal algorithms for testing closeness of discrete distributions","author":"Chan","year":"2014","journal-title":"Proceedings of SODA"},{"key":"2026032712183032800_ref038","author":"Cover","journal-title":"Elements of information theory"},{"issue":"20","key":"2026032712183032800_ref039","doi-asserted-by":"publisher","first-page":"535","DOI":"10.4086\/toc.2014.v010a020","article-title":"Learning k-modal distributions via testing","volume":"10","author":"Daskalakis","year":"2014","journal-title":"Theory of Computing"},{"issue":"1","key":"2026032712183032800_ref040","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/s00453-015-9971-3","article-title":"Learning Poisson Binomial Distributions","volume":"72","author":"Daskalakis","year":"2015","journal-title":"Algorithmica"},{"key":"2026032712183032800_ref041","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1145\/3406325.3450997","article-title":"Optimal testing of discrete distributions with high probability","author":"Diakonikolas","year":"2021","journal-title":"STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021"},{"key":"2026032712183032800_ref042","article-title":"Communication and memory efficient testing of discrete distributions","author":"Diakonikolas","journal-title":"COLT"},{"key":"2026032712183032800_ref043","article-title":"Sampleoptimal identity testing with high probability","author":"Diakonikolas","journal-title":"45th International Colloquium on Automata, Languages, and Programming"},{"key":"2026032712183032800_ref044","doi-asserted-by":"publisher","article-title":"Collisionbased testers are optimal for uniformity and closeness","author":"Diakonikolas","DOI":"10.4086\/cjtcs.2019.001"},{"key":"2026032712183032800_ref045","doi-asserted-by":"crossref","DOI":"10.1109\/FOCS.2016.78","article-title":"A new approach for testing properties of discrete distributions","author":"Diakonikolas","year":"2016","journal-title":"57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016"},{"key":"2026032712183032800_ref046","article-title":"Testing Identity of Structured Distributions","author":"Diakonikolas","year":"2015","journal-title":"Proceedings of SODA"},{"issue":"2","key":"2026032712183032800_ref047","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2&lt;99::AID-RSA1&gt;3.0.CO;2-M","article-title":"Balls and bins: A study in negative dependence","volume":"13","author":"Dubhashi","year":"1998","journal-title":"Random Structures Algorithms"},{"key":"2026032712183032800_ref048","doi-asserted-by":"publisher","author":"Dubhashi","journal-title":"Concentration of measure for the analysis of randomized algorithms","DOI":"10.1017\/CBO9780511581274"},{"key":"2026032712183032800_ref049","article-title":"Lower bounds for locally private estimation via communication complexity","author":"Duchi","year":"2019","journal-title":"Proceedings of the Thirty-Second Conference on Learning Theory"},{"key":"2026032712183032800_ref050","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1109\/FOCS.2013.53","article-title":"Local privacy and statistical minimax rates","author":"Duchi","year":"2013","journal-title":"54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013"},{"key":"2026032712183032800_ref051","doi-asserted-by":"crossref","article-title":"Minimax optimal procedures for locally private estimation","author":"Duchi","DOI":"10.1080\/01621459.2017.1389735"},{"key":"2026032712183032800_ref052","article-title":"Calibrating noise to sensitivity in private data analysis","author":"Dwork","journal-title":"Theory of cryptography"},{"key":"2026032712183032800_ref053","first-page":"455","article-title":"Distributed uniformity testing","author":"Fischer","year":"2018","journal-title":"Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018"},{"key":"2026032712183032800_ref054","first-page":"2726","article-title":"On communication cost of distributed statistical estimation and dimensionality","author":"Garg","year":"2014","journal-title":"Advances in Neural Information Processing Systems 27"},{"key":"2026032712183032800_ref055","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.PPROX-RANDOM.2014.704","article-title":"On Multiple Input Problems in Property Testing","author":"Goldreich","year":"2014","journal-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2014)"},{"key":"2026032712183032800_ref056","article-title":"The uniform distribution is complete with respect to testing identity to a fixed distribution","volume":"23","author":"Goldreich","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"2026032712183032800_ref057","author":"Goldreich","journal-title":"Introduction to Property Testing"},{"issue":"4","key":"2026032712183032800_ref058","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","article-title":"Property testing and its connection to learning and approximation","volume":"45","author":"Goldreich","year":"1998","journal-title":"Journal of the ACM"},{"issue":"20","key":"2026032712183032800_ref059","article-title":"On testing expansion in boundeddegree graphs","volume":"7","author":"Goldreich","year":"2000","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"12","key":"2026032712183032800_ref060","doi-asserted-by":"crossref","first-page":"8157","DOI":"10.1109\/TIT.2013.2283266","article-title":"Generalized error exponents for small sample universal hypothesis testing","volume":"59","author":"Huang","year":"2013","journal-title":"IEEE Transactions on Information Theory"},{"key":"2026032712183032800_ref061","article-title":"A minimax test of nonparametric hypotheses on the density of a distribution in Lp metrics","author":"Ingster"},{"key":"2026032712183032800_ref062","doi-asserted-by":"publisher","DOI":"10.1007\/BF02673632","article-title":"Adaptive chi-square tests","volume":"244","author":"Ingster","journal-title":"Zap. Nauchn. Sem. S.Peterburg. Otdel. Mat. Inst. Steklov. (POMI)"},{"key":"2026032712183032800_ref063","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-21580-8","volume":"169","author":"Ingster","journal-title":"Nonparametric goodness-of-fit testing under Gaussian models"},{"key":"2026032712183032800_ref064","article-title":"A primer on private statistics","author":"Kamath","journal-title":"CoRR"},{"key":"2026032712183032800_ref065","article-title":"On learning distributions from their samples","author":"Kamath","journal-title":"Proceedings of the 28th Conference on Learning Theory, COLT 2015"},{"key":"2026032712183032800_ref066","author":"Kasiviswanathan"},{"key":"2026032712183032800_ref067","article-title":"Convergence of estimates under dimensionality restrictions","author":"Le Cam"},{"key":"2026032712183032800_ref068","doi-asserted-by":"publisher","author":"Meir","DOI":"10.1145\/3293611.3331613"},{"key":"2026032712183032800_ref069","author":"Nazarov"},{"key":"2026032712183032800_ref070","article-title":"Probability-revealing samples","author":"Onak","journal-title":"International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain"},{"issue":"10","key":"2026032712183032800_ref071","doi-asserted-by":"crossref","first-page":"4750","DOI":"10.1109\/TIT.2008.928987","article-title":"A coincidence-based test for uniformity given very sparsely sampled discrete data","volume":"54","author":"Paninski","year":"2008","journal-title":"IEEE Transactions on Information Theory"},{"issue":"6","key":"2026032712183032800_ref072","doi-asserted-by":"crossref","first-page":"1012","DOI":"10.1016\/j.jcss.2006.03.002","article-title":"Tolerant property testing and distance approximation","volume":"72","author":"Parnas","year":"2006","journal-title":"Journal of Computer and System Sciences"},{"issue":"302","key":"2026032712183032800_ref073","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1080\/14786440009463897","article-title":"X. on the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling","volume":"50","author":"Pearson","year":"1900","journal-title":"The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science"},{"key":"2026032712183032800_ref074","author":"Pollard","year":"2003","journal-title":"Asymptopia"},{"issue":"1","key":"2026032712183032800_ref075","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1002\/rsa.v34:1","article-title":"Testing monotone high-dimensional distributions","volume":"34","author":"Rubinfeld","year":"2009","journal-title":"Random Structures and Algorithms"},{"key":"2026032712183032800_ref076","author":"Schauer","journal-title":"Stochastic dominance between (products of) binomials"},{"key":"2026032712183032800_ref077","first-page":"163","article-title":"Fundamental limits of online and distributed algorithms for statistical learning and estimation","author":"Shamir","year":"2014","journal-title":"Advances in Neural Information Processing Systems 27"},{"key":"2026032712183032800_ref078","article-title":"Birthday paradox for multi-collisions","author":"Suzuki","journal-title":"Information security and cryptology\u2014ICISC 2006"},{"key":"2026032712183032800_ref079","first-page":"297","article-title":"Decentralized detection","volume":"2","author":"Tsitsiklis","year":"1993","journal-title":"Advances in Statistical Signal Processing"},{"key":"2026032712183032800_ref080","doi-asserted-by":"publisher","author":"Tsybakov","journal-title":"Introduction to nonparametric estimation","DOI":"10.1007\/b13794"},{"key":"2026032712183032800_ref081","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1145\/1993636.1993727","article-title":"Estimating the unseen: An n\/ log nsample estimator for entropy and support size, shown optimal via new clts","author":"Valiant","year":"2011","journal-title":"Symposium on Theory of Computing Conference, STOC\u201911"},{"key":"2026032712183032800_ref082","doi-asserted-by":"crossref","DOI":"10.1109\/FOCS.2014.14","article-title":"An automatic inequality prover and instance optimal identity testing","author":"Valiant","year":"2014","journal-title":"55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014"},{"issue":"1","key":"2026032712183032800_ref083","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1137\/151002526","article-title":"An automatic inequality prover and instance optimal identity testing","volume":"46","author":"Valiant","year":"2017","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"2026032712183032800_ref084","doi-asserted-by":"crossref","first-page":"1927","DOI":"10.1137\/080734066","article-title":"Testing symmetric properties of distributions","volume":"40","author":"Valiant","year":"2011","journal-title":"SIAM Journal on Computing"},{"key":"2026032712183032800_ref085","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596","volume":"47","author":"Vershynin","journal-title":"High-dimensional probability"},{"issue":"4","key":"2026032712183032800_ref086","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1561\/0100000095","article-title":"Polynomial methods in statistical inference: Theory and practice","volume":"17","author":"Wu","year":"2020","journal-title":"Found. Trends Commun. Inf. Theory"},{"issue":"8","key":"2026032712183032800_ref087","doi-asserted-by":"publisher","first-page":"5662","DOI":"10.1109\/TIT.2018.2809790","article-title":"Optimal schemes for discrete distribution estimation under locally differential privacy","volume":"64","author":"Ye","year":"2018","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2026032712183032800_ref088","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1880-7_29","article-title":"Assouad, Fano, and Le Cam","author":"Yu","journal-title":"Festschrift for Lucien Le Cam"},{"key":"2026032712183032800_ref089","first-page":"2328","article-title":"Information-theoretic lower bounds for distributed statistical estimation with communication constraints","author":"Zhang","year":"2013","journal-title":"Advances in Neural Information Processing Systems 26"}],"container-title":["Foundations and Trends\u00ae in Communications and Information Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/ftcit\/article-pdf\/19\/6\/1032\/11163319\/0100000114en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/ftcit\/article-pdf\/19\/6\/1032\/11163319\/0100000114en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T14:10:44Z","timestamp":1777471844000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/ftcit\/article\/19\/6\/1032\/1333183\/Topics-and-Techniques-in-Distribution-Testing-A"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,22]]},"references-count":89,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,11,22]]}},"URL":"https:\/\/doi.org\/10.1561\/0100000114","relation":{},"ISSN":["1567-2190","1567-2328"],"issn-type":[{"value":"1567-2190","type":"print"},{"value":"1567-2328","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,22]]}}}