A Survey on Distribution Testing: Bibliographical Information

[AAK+07] Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie. Testing k-wise and almost k-wise independence. In Proceedings of STOC, pages 496--505, New York, NY, USA, 2007. [ bib | DOI | http ]
[ABR16] Maryam Aliakbarpour, Eric Blais, and Ronitt Rubinfeld. Learning and testing junta distributions. In Proceedings of COLT, volume 49 of JMLR Workshop and Conference Proceedings, pages 19--46. JMLR.org, 2016. [ bib ]
[ACK14] Jayadev Acharya, Clément L. Canonne, and Gautam Kamath. A chasm between identity and equivalence testing with conditional queries. ArXiV, abs/1411.7346, November 2014. [ bib ]
[ACS10] Michat Adamaszek, Artur Czumaj, and Christian Sohler. Testing monotone continuous distributions on high-dimensional real cubes. In Proceedings of SODA, pages 56--65. Society for Industrial and Applied Mathematics, 2010. [ bib | http ]
[AD14] Jayadev Acharya and Constantinos Daskalakis. Testing Poisson Binomial Distributions. In Proceedings of SODA, pages 1829--1840, 2014. [ bib ]
[ADJ+11] Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, and Shengjun Pan. Competitive closeness testing. In Proceedings of COLT, pages 47--68, 2011. [ bib ]
[ADJ+12] Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan, and Ananda Theertha Suresh. Competitive classification and closeness testing. In Proceedings of COLT, volume 23, pages 22.1--22.18, 2012. [ bib ]
[ADK15] Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. In C. Cortes, N.D. Lawrence, D.D. Lee, M. Sugiyama, R. Garnett, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 3577--3598. Curran Associates, Inc., 2015. [ bib | .pdf ]
[AJ06] José A. Adell and Pedro Jodra. Exact Kolmogorov and total variation distances between some familiar discrete distributions. Journal of Inequalities and Applications, 2006(1):64307, 2006. [ bib | DOI ]
[AJOS13] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. A competitive test for uniformity of monotone distributions. In Proceedings of AISTATS, pages 57--65, 2013. [ bib ]
[AJOS14] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Sublinear algorithms for outlier detection and generalized closeness testing. In 2014 IEEE International Symposium on Information Theory (ISIT), pages 3200--3204. IEEE, 2014. [ bib | DOI | http ]
[An96] Mark Y. An. Log-concave probability distributions: theory and statistical testing. Technical report, Centre for Labour Market and Social Research, Denmark, 1996. [ bib | http ]
[AOST15] Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. The complexity of estimating Rényi entropy. In Proceedings of SODA, pages 1855--1869. Society for Industrial and Applied Mathematics (SIAM), 2015. [ bib ]
[Ass83] Patrice Assouad. Deux remarques sur l'estimation. Comptes Rendus des Séances de l'Académie des Sciences. Série I. Mathématique, 296(23):1021--1024, 1983. [ bib ]
[BBM12] Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. Computational Complexity, 21(2):311--358, 2012. [ bib | DOI | http ]
[BCG16] Eric Blais, Clément Louis Canonne, and Tom Gur. Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.). Electronic Colloquium on Computational Complexity (ECCC), 23:168, 2016. [ bib ]
[BDKR05] Tuğkan Batu, Sanjoy Dasgupta, Ravi Kumar, and Ronitt Rubinfeld. The complexity of approximating the entropy. SIAM Journal on Computing, 35(1):132--150, 2005. [ bib ]
[BFF+01] Tuğkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. Testing random variables for independence and identity. In Proceedings of FOCS, pages 442--451, 2001. [ bib ]
[BFR+00] Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing that distributions are close. In Proceedings of FOCS, pages 189--197, 2000. [ bib ]
[BFR+13] Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing closeness of discrete distributions. Journal of the ACM, 60(1):4:1--4:25, February 2013. This is the journal version of [BFR+00]. [ bib ]
[BFRV11] Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, and Paul Valiant. Testing monotonicity of distributions over general partial orders. In Proceedings of ITCS, pages 239--252, 2011. [ bib ]
[Bir87] Lucien Birgé. On the risk of histograms for estimating decreasing densities. The Annals of Mathematical Statistics, 15(3):pp. 1013--1022, 1987. [ bib | http ]
[BKR04] Tuğkan Batu, Ravi Kumar, and Ronitt Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. In Proceedings of STOC, pages 381--390, New York, NY, USA, 2004. ACM. [ bib | DOI | http ]
[BLR93] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences, 47:549--595, 1993. An earlier version of this work appeared in STOC'90. [ bib ]
[BRY14] Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lp-testing. In Proceedings of STOC, pages 164--173, New York, NY, USA, 2014. ACM. [ bib | DOI | http ]
[BV15] Bhaswar Bhattacharya and Gregory Valiant. Testing closeness with unequal sized samples. In C. Cortes, N.D. Lawrence, D.D. Lee, M. Sugiyama, R. Garnett, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 2593--2601. Curran Associates, Inc., 2015. [ bib | .pdf ]
[BY02] Ziv Bar-Yossef. The Complexity of Massive Data Set Computations. PhD thesis, UC Berkeley, 2002. Adviser: Christos Papadimitriou. Available at http://webee.technion.ac.il/people/zivby/index_files/Page1489.html. [ bib ]
[Can13] Clément L. Canonne. Dompter les Distributions de Probabilité Géantes. http://www.cs.columbia.edu/~ccanonne/files/misc/tamingbigdistr-fr.pdf, 2013. French translation of [Rub12]. [ bib ]
[Can15] Clément L. Canonne. Big Data on the rise? Testing monotonicity of distributions. In Proceedings of ICALP, volume 9134 of Lecture Notes in Computer Science, pages 294--305. Springer, 2015. Also available on arXiv at abs/1501.06783. [ bib | DOI | http ]
[Can16] Clément L. Canonne. Are Few Bins Enough: Testing Histogram Distributions. In Proceedings of PODS. Association for Computing Machinery (ACM), 2016. [ bib | DOI | http ]
[CDGR16] Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, and Ronitt Rubinfeld. Testing Shape Restrictions of Discrete Distributions. In 33rd International Symposium on Theoretical Aspects of Computer Science (STACS), 2016. See also [CDGR17] (full version). [ bib ]
[CDGR17] Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, and Ronitt Rubinfeld. Testing shape restrictions of discrete distributions. Theory of Computing Systems, pages 1--59, 2017. Also available on arXiv at abs/1507.03558. [ bib | DOI | http ]
[CDSS13] Siu-On Chan, Ilias Diakonikolas, Rocco A. Servedio, and Xiaorui Sun. Learning mixtures of structured distributions over discrete domains. In Proceedings of SODA, pages 1380--1394, 2013. [ bib ]
[CDSS14] Siu-On Chan, Ilias Diakonikolas, Rocco A. Servedio, and Xiaorui Sun. Efficient density estimation via piecewise polynomial approximation. In Proceedings of STOC, pages 604--613. ACM, 2014. [ bib ]
[CDVV14] Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, and Paul Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of SODA, pages 1193--1203. Society for Industrial and Applied Mathematics (SIAM), 2014. [ bib ]
[CFGM13] Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah. On the power of conditional samples in distribution testing. In Proceedings of ITCS, pages 561--580, New York, NY, USA, 2013. ACM. [ bib | DOI | http ]
[CGR16] Clément L. Canonne, Themis Gouleakis, and Ronitt Rubinfeld. Sampling Correctors. In Proceedings of ITCS, pages 93--102. ACM, 2016. [ bib ]
[CKOS15] Cafer Caferov, Baris Kaya, Ryan O'Donnell, and A. C. Cem Say. Optimal bounds for estimating entropy with PMF queries. In MFCS (2), volume 9235 of Lecture Notes in Computer Science, pages 187--198. Springer, 2015. [ bib ]
[CR14] Clément L. Canonne and Ronitt Rubinfeld. Testing probability distributions underlying aggregated data. In Proceedings of ICALP, pages 283--295, 2014. [ bib ]
[CRS13] Clément L. Canonne, Dana Ron, and Rocco A. Servedio. Private communication, 2013. [ bib ]
[CRS14] Clément L. Canonne, Dana Ron, and Rocco A. Servedio. Testing equivalence between distributions using conditional samples. In Proceedings of SODA, pages 1174--1192. Society for Industrial and Applied Mathematics (SIAM), 2014. See also [CRS15] (full version). [ bib | http ]
[CRS15] Clément L. Canonne, Dana Ron, and Rocco A. Servedio. Testing probability distributions using conditional samples. SIAM Journal on Computing, 44(3):540--616, 2015. Also available on arXiv at abs/1211.2664. [ bib | DOI ]
[DBNNR11] Khanh Do Ba, Huy L. Nguyen, Huy N. Nguyen, and Ronitt Rubinfeld. Sublinear time algorithms for Earth Mover's distance. Theory of Computing Systems, 48(2):428--442, 2011. [ bib ]
[DD09] Yuxin Deng and Wenjie Du. The Kantorovich metric in computer science: A brief survey. Electronic Notes in Theoretical Computer Science, 253(3):73 -- 82, 2009. Proceedings of Seventh Workshop on Quantitative Aspects of Programming Languages (QAPL 2009). [ bib | DOI | http ]
[DDO+13] Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, and Li-Yang Tan. Learning Sums of Independent Integer Random Variables. In Proceedings of FOCS, pages 217--226. IEEE Computer Society, 2013. [ bib ]
[DDS12a] Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. Learning k-modal distributions via testing. In Proceedings of SODA, pages 1371--1385. Society for Industrial and Applied Mathematics (SIAM), 2012. [ bib | http ]
[DDS12b] Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. Learning Poisson Binomial Distributions. In Proceedings of STOC, STOC '12, pages 709--728, New York, NY, USA, 2012. ACM. [ bib ]
[DDS+13] Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, and Paul Valiant. Testing k-modal distributions: Optimal algorithms via reductions. In Proceedings of SODA, pages 1833--1852. Society for Industrial and Applied Mathematics (SIAM), 2013. [ bib | http ]
[DGPP16] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Collision-based Testers are Optimal for Uniformity and Closeness. ArXiV, abs/1611.03579, 2016. [ bib ]
[DK16] Ilias Diakonikolas and Daniel M. Kane. A new approach for testing properties of discrete distributions. In Proceedings of FOCS. IEEE Computer Society, 2016. [ bib ]
[DKN15a] Ilias Diakonikolas, Daniel M. Kane, and Vladimir Nikishkin. Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions. In Proceedings of FOCS, 2015. [ bib ]
[DKN15b] Ilias Diakonikolas, Daniel M. Kane, and Vladimir Nikishkin. Testing Identity of Structured Distributions. In Proceedings of SODA, pages 1841--1854. Society for Industrial and Applied Mathematics (SIAM), 2015. [ bib ]
[DKW56] Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, 27(3):642--669, 09 1956. [ bib | DOI | http ]
[DL01] Luc Devroye and Gábor Lugosi. Combinatorial Methods in Density Estimation. Springer Series in Statistics. Springer New York, 2001. [ bib | http ]
[Fis01] Eldar Fischer. The art of uninformed decisions: A primer to property testing. Bulletin of the European Association for Theoretical Computer Science, 75:97--126, 2001. [ bib ]
[FJO+15] Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapathi, and Ananda Theertha Suresh. Faster algorithms for testing under conditional sampling. In Proceedings of COLT, JMLR Proceedings, pages 607--636, 2015. [ bib ]
[GGR98] Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45(4):653--750, July 1998. [ bib ]
[Gly87] Peter W. Glynn. Upper bounds on Poisson tail probabilities. Operations Research Letters, 6(1):9--14, March 1987. [ bib | DOI | http ]
[GMV06] Sudipto Guha, Andrew McGregor, and Suresh Venkatasubramanian. Streaming and sublinear approximation of entropy and information distances. In Proceedings of SODA, pages 733--742, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics (SIAM). [ bib | http ]
[Gol10] Oded Goldreich, editor. Property Testing: Current Research and Surveys. Springer, 2010. LNCS 6390. [ bib ]
[Gol13] Oded Goldreich. On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing. Electronic Colloquium on Computational Complexity (ECCC), 20:73, 2013. [ bib ]
[Gol16] Oded Goldreich. The uniform distribution is complete with respect to testing identity to a fixed distribution. Electronic Colloquium on Computational Complexity (ECCC), 23:15, 2016. [ bib ]
[GR00] Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. Electronic Colloquium on Computational Complexity (ECCC), 7:20, 2000. [ bib ]
[GR13] Oded Goldreich and Dana Ron. On Sample-Based Testers. Electronic Colloquium on Computational Complexity (ECCC), 20:109, 2013. [ bib ]
[GS02] Alison L. Gibbs and Francis E. Su. On choosing and bounding probability metrics. Interdisciplinary Science Reviews, 70:419--435, December 2002. [ bib | DOI | arXiv ]
[GV11] Oded Goldreich and Salil P. Vadhan. On the complexity of computational problems regarding distributions. In Oded Goldreich, editor, Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, volume 6650 of Lecture Notes in Computer Science, pages 390--405. Springer, 2011. [ bib | http ]
[Har15] Sariel Har-Peled. Lower bound on estimating Σk=1n ak for non-increasing (ak)k. Theoretical Computer Science Stack Exchange, January 2015. http://cstheory.stackexchange.com/q/28024 (version: 2015-01-01). [ bib | http ]
[ILR12] Piotr Indyk, Reut Levi, and Ronitt Rubinfeld. Approximating and Testing k-Histogram Distributions in Sub-linear Time. In Proceedings of PODS, pages 15--22, 2012. [ bib ]
[JHW16] Jiantao Jiao, Yanjun Han, and Tsachy Weissman. Minimax estimation of the l1 distance. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 750--754, July 2016. [ bib | DOI ]
[JVW14] Jiantao Jiao, Kartik Venkat, and Tsachy Weissman. Order-optimal estimation of functionals of discrete distributions. ArXiV, abs/1406.6956, 2014. [ bib | http ]
[KR58] Leonid Kantorovich and Gennady S. Rubinstein. On a space of totally additive functions. Vestnik Leningrad. Univ, 13:52--59, 1958. [ bib ]
[LC60] Lucien Le Cam. An approximation theorem for the Poisson binomial distribution. Pacific Journal of Mathematics, 10(4):1181--1197, 1960. [ bib | http ]
[LC73] Lucien Le Cam. Convergence of estimates under dimensionality restrictions. The Annals of Mathematical Statistics, 1:38--53, 1973. [ bib ]
[LC86] Lucien Le Cam. Asymptotic methods in statistical decision theory. Springer Series in Statistics. Springer-Verlag, New York, 1986. [ bib | DOI | http ]
[LRR13] Reut Levi, Dana Ron, and Ronitt Rubinfeld. Testing properties of collections of distributions. Theory of Computing, 9:295--347, 2013. [ bib | DOI | http ]
[LRR14] Reut Levi, Dana Ron, and Ronitt Rubinfeld. Testing similar means. SIAM Journal on Discrete Math, 28(4):1699--1724, 2014. [ bib | DOI | http ]
[Ma81] Shang-Keng Ma. Calculation of entropy from data of motion. Journal of Statistical Physics, 26(2):221--240, 1981. [ bib | DOI | http ]
[Mas90] Pascal Massart. The tight constant in the Dvoretzky--Kiefer--Wolfowitz inequality. The Annals of Probability, 18(3):1269--1283, 07 1990. [ bib | DOI | http ]
[MWolfW13] Ashley Montanaro and Ronald Wolfde Wolf. A Survey of Quantum Property Testing. ArXiV, abs/1310.2035, October 2013. [ bib ]
[OW15] Ryan O'Donnell and John Wright. Quantum Spectrum Testing. ArXiV, abs/1501.05028, January 2015. [ bib ]
[Pan04] Liam Paninski. Estimating entropy on m bins given fewer than m samples. IEEE Transactions on Information Theory, 50(9):2200--2203, 2004. [ bib ]
[Pan08] Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Transactions on Information Theory, 54(10):4750--4755, 2008. [ bib ]
[Poi37] Siméon Denis Poisson. Recherches sur la probabilité des jugements en matière criminelle et en matière civile: précédées des règles générales du calcul des probabilités. Bachelier, 1837. [ bib | http ]
[Pol03] David Pollard. Asymptopia. http://www.stat.yale.edu/~pollard/Books/Asymptopia, 2003. Manuscript. [ bib ]
[PRR06] Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 72(6):1012--1042, 2006. [ bib ]
[Reb05] Laurence Reboul. Estimation of a function under shape restrictions. applications to reliability. The Annals of Mathematical Statistics, 33(3):1330--1356, 06 2005. [ bib | http ]
[Rey11] Leo Reyzin. Extractors and the leftover hash lemma. http://www.cs.bu.edu/~reyzin/teaching/s11cs937/notes-leo-1.pdf, March 2011. Lecture notes. [ bib ]
[Ron08] Dana Ron. Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning, 1(3):307--402, 2008. [ bib ]
[Ron10] Dana Ron. Algorithmic and analysis techniques in property testing. Foundations and Trends in Theoretical Computer Science, 5:73--205, 2010. [ bib ]
[RRSS09] Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith. Strong lower bounds for approximating distributions support size and the distinct elements problem. SIAM Journal on Computing, 39(3):813--842, 2009. [ bib ]
[RS96] Ronitt Rubinfeld and Madhu Sudan. Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252--271, 1996. [ bib ]
[RS09] Ronitt Rubinfeld and Rocco A. Servedio. Testing monotone high-dimensional distributions. Random Structures and Algorithms, 34(1):24--44, January 2009. [ bib | DOI ]
[Rub12] Ronitt Rubinfeld. Taming Big Probability Distributions. XRDS, 19(1):24--28, September 2012. [ bib | DOI | http ]
[RX10] Ronitt Rubinfeld and Ning Xie. Testing non-uniform k-wise independent distributions over product spaces. In Proceedings of ICALP, pages 565--581, Berlin, Heidelberg, 2010. Springer-Verlag. [ bib | http ]
[Sch47] Henry Scheffé. A useful convergence theorem for probability distributions. The Annals of Mathematical Statistics, 18(3):434--438, 09 1947. [ bib | DOI | http ]
[SV03] Amit Sahai and Salil Vadhan. A complete problem for Statistical Zero Knowledge. Journal of the ACM, 50(2):196--249, March 2003. [ bib | DOI | http ]
[Szp01] Wojciech Szpankowski. Average Case Analysis of Algorithms on Sequences, chapter Analytic Poissonization and Depoissonization, pages 442--519. John Wiley & Sons, Inc., 2001. [ bib | DOI | http ]
[Val11] Paul Valiant. Testing symmetric properties of distributions. SIAM Journal on Computing, 40(6):1927--1968, 2011. [ bib ]
[Val12] Gregory Valiant. Algorithmic Approaches to Statistical Questions. PhD thesis, UC Berkeley, 2012. Adviser: Christos Papadimitriou. [ bib ]
[VV10a] Gregory Valiant and Paul Valiant. A CLT and tight lower bounds for estimating entropy. Electronic Colloquium on Computational Complexity (ECCC), 17:179, 2010. [ bib ]
[VV10b] Gregory Valiant and Paul Valiant. Estimating the unseen: A sublinear-sample canonical estimator of distributions. Electronic Colloquium on Computational Complexity (ECCC), 17:180, 2010. [ bib ]
[VV11] Gregory Valiant and Paul Valiant. The power of linear estimators. In Proceedings of FOCS, pages 403--412, October 2011. See also [VV10a] and [VV10b]. [ bib | DOI ]
[VV14] Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. In Proceedings of FOCS, 2014. See also [VV17] (full version). [ bib ]
[VV17] Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. SIAM Journal on Computing, 46(1):429--455, 2017. [ bib | DOI | arXiv ]
[Wag15] Bo Waggoner. L_p testing and learning of discrete distributions. In Proceedings of ITCS, pages 347--356. ACM, 2015. [ bib | DOI | http ]
[Wal09] Guenther Walther. Inference and modeling with log-concave distributions. Statistical Science, 24(3):319--327, 08 2009. [ bib | DOI | http ]
[WY16] Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory, 62(6):3702--3720, 2016. [ bib ]
[Yu97] Bin Yu. Assouad, Fano, and Le Cam. In David Pollard, Erik Torgersen, and Grace L. Yang, editors, Festschrift for Lucien Le Cam, pages 423--435. Springer New York, 1997. [ bib | DOI | http ]

This file was generated by bibtex2html 1.98.