[1]   List of Open Problems in Sublinear Algorithms: Problem 66. Bertinoro Workshop on Sublinear Algorithms 2014 (suggested by Eldar Fischer). Available at http://sublinear.info/66.

[2]   Jayadev Acharya, Clément L. Canonne, and Gautam Kamath: Adaptive estimation in weighted group testing. In IEEE Internat. Symp. Information Theory (ISIT’15), pp. 2116–2120, 2015. [doi:10.1109/ISIT.2015.7282829]

[3]   Jayadev Acharya, Clément L. Canonne, and Gautam Kamath: A chasm between Identity and Equivalence Testing with conditional queries. In Proc. 19th Internat. Workshop on Randomization and Computation (RANDOM’15), volume 40, pp. 449–466. Schloss Dagstuhl, 2015. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.449, arXiv:1411.7346, ECCC:TR14-156]

[4]   Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, and Shengjun Pan: Competitive closeness testing. In Proc. 24th Ann. Conf. on Learning Theory (COLT’11), volume 19 of JMLR Proceedings, pp. 47–68. JMLR.org, 2011. Accessible at JMLR.

[5]   Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan, and Ananda Theertha Suresh: Competitive classification and closeness testing. In Proc. 25th Ann. Conf. on Learning Theory (COLT’12), pp. 22.1–22.18, 2012. Accessible at JMLR.

[6]   Anne Auger and Benjamin Doerr: Theory of Randomized Search Heuristics: Foundations and Recent Developments. Series on theoretical computer science. World Scientific, 2011.

[7]   Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang: Active property testing. In Proc. 53rd FOCS, pp. 21–30. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.64]

[8]   Tuğkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White: Testing random variables for independence and identity. In Proc. 42nd FOCS, pp. 442–451. IEEE Comp. Soc. Press, 2001. [doi:10.1109/SFCS.2001.959920]

[9]   Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White: Testing that distributions are close. In Proc. 41st FOCS, pp. 189–197. IEEE Comp. Soc. Press, 2000. This is a preliminary version of [10]. [doi:10.1109/SFCS.2000.892113]

[10]   Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White: Testing closeness of discrete distributions. 2010. This is a long version of [9]. [arXiv:1009.5397]

[11]   Tuğkan Batu, Ravi Kumar, and Ronitt Rubinfeld: Sublinear algorithms for testing monotone and unimodal distributions. In Proc. 36th STOC, pp. 381–390. ACM Press, 2004. [doi:10.1145/1007352.1007414]

[12]   Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, and Paul Valiant: Testing monotonicity of distributions over general partial orders. In Proc. 2nd Conf. on Innovations in Theoret. Comput. Sci. (ITCS’11), pp. 239–252, 2011. [ECCC:TR10-027]

[13]   Clément L. Canonne: A survey on distribution testing: Your data is Big, but is it Blue? Electron. Colloq. on Comput. Complexity (ECCC), April 2015. [ECCC:TR15-063]

[14]   Clément L. Canonne, Dana Ron, and Rocco A. Servedio: Testing probability distributions using conditional samples. SIAM J. Comput., 44(3):540–616, 2015. Preliminary version in SODA’14. [doi:10.1137/130945508, arXiv:1211.2664, ECCC:TR12-155]

[15]   Clément L. Canonne and Ronitt Rubinfeld: Testing probability distributions underlying aggregated data. In Proc. 41st Internat. Colloq. on Automata, Languages and Programming (ICALP’14), pp. 283–295. Springer, 2014. [doi:10.1007/978-3-662-43948-7_24, arXiv:1402.3835, ECCC:TR14-021]

[16]   Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah: On the power of conditional samples in distribution testing. SIAM J. Comput., 45(4):1261–1296, 2016. Preliminary version in ITCS’13. [doi:10.1137/140964199, arXiv:1210.8338, ECCC:TR12-154]

[17]   Chun Lam Chan, Sidharth Jaggi, Venkatesh Saligrama, and Samar Agnihotri: Non-adaptive group testing: Explicit bounds and novel algorithms. IEEE Trans. Inform. Theory, 60(5):3019–3035, 2014. Preliminary version in ISIT’12. [doi:10.1109/TIT.2014.2310477, arXiv:1202.0206]

[18]   Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, and Paul Valiant: Optimal algorithms for testing closeness of discrete distributions. In Proc. 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’14), pp. 1193–1203. ACM Press, 2014. [doi:10.1137/1.9781611973402.88, arXiv:1308.3946]

[19]   Vašek Chvátal: The tail of the hypergeometric distribution. Discrete Mathematics, 25(3):285 – 287, 1979. [doi:10.1016/0012-365X(79)90084-0]

[20]   Sanjoy Dasgupta: Analysis of a greedy active learning strategy. In Advances in Neural Information Processing Systems 17, pp. 337–344. MIT Press, 2004–2005. Available at NIPS.

[21]   Robert Dorfman: The detection of defective members of large populations. Ann. Math. Statist., 14(4):436–440, 1943. [doi:10.1214/aoms/1177731363]

[22]   Dingzhu Du and Frank K. Hwang: Combinatorial Group Testing and Its Applications. Applied Mathematics. World Scientific, 2000.

[23]   Devdatt P. Dubhashi and Desh Ranjan: Balls and Bins: A study in negative dependence. Random Structures Algorithms, 13(2):99–124, 1996. [doi:10.1002/(SICI)1098-2418(199809)13:2¡99::AID-RSA1¿3.0.CO;2-M]

[24]   Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapathi, and Ananda Theertha Suresh: Faster algorithms for testing under conditional sampling. In Proc. 28th Ann. Conf. on Learning Theory (COLT’15), JMLR Proceedings, pp. 607–636, 2015. [arXiv:1504.04103]

[25]   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.

[26]   Oded Goldreich, editor. Property Testing: Current Research and Surveys. Springer, 2010. LNCS 6390. [doi:10.1007/978-3-642-16367-8]

[27]   Oded Goldreich and Dana Ron: On testing expansion in bounded-degree graphs. Technical report, Electron. Colloq. on Comput. Complexity (ECCC), 2000. [ECCC:TR00-020]

[28]   Sudipto Guha, Andrew McGregor, and Suresh Venkatasubramanian: Sublinear estimation of entropy and information distances. ACM Trans. Algorithms, 2009. Preliminary version in SODA’06. [doi:10.1145/1597036.1597038, arXiv:cs/0508122]

[29]   Piotr Indyk, Reut Levi, and Ronitt Rubinfeld: Approximating and testing k-histogram distributions in sub-linear time. In Proc. 31st Symp. on Principles of Database Systems (PODS’12), pp. 15–22, 2012. [doi:10.1145/2213556.2213561, ECCC:TR11-171]

[30]   Reut Levi, Dana Ron, and Ronitt Rubinfeld: Testing properties of collections of distributions. Theory of Computing, 9(8):295–347, 2013. Preliminary version in ICS’11. [doi:10.4086/toc.2013.v009a008, ECCC:TR10-157]

[31]   Rajeev Motwani and Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1995.

[32]   Hung Q. Ngo and Ding-Zhu Du: A Survey on Combinatorial Group Testing Algorithms with Applications to DNA Library Screening. In DIMACS Ser. in Discr. Math. and Theoret. Comput. Sci., number 2, 2000.

[33]   Liam Paninski: A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Trans. Inform. Theory, 54(10):4750–4755, 2008. [doi:10.1109/TIT.2008.928987]

[34]   Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith: Strong lower bounds for approximating distributions support size and the distinct elements problem. SIAM J. Comput., 39(3):813–842, 2009. Preliminary version in FOCS’07. [doi:10.1137/070701649]

[35]   Dana Ron: Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning, 1(3):307–402, 2008. Preliminary version in COLT’07. [doi:10.1561/2200000004]

[36]   Dana Ron: Algorithmic and analysis techniques in property testing. Found. Trends Theor. Comput. Sci., 5:73–205, 2010. [doi:10.1561/0400000029]

[37]   Dana Ron and Gilad Tsur: The power of an example: Hidden set size approximation using group queries and conditional sampling. ACM Trans. Comput. Theory, 8(4):15:1–15:19, 2016. [doi:10.1145/2930657, arXiv:1404.5568]

[38]   Ronitt Rubinfeld: Taming Big Probability Distributions. XRDS, 19(1):24–28, 2012. [doi:10.1145/2331042.2331052]

[39]   Ronitt Rubinfeld and Rocco A. Servedio: Testing monotone high-dimensional distributions. Random Structures Algorithms, 34(1):24–44, January 2009. Preliminary version in STOC’05. [doi:10.1002/rsa.20247]

[40]   Burr Settles: Active learning literature survey. CS Technical Reports 1648, University of Wisconsin–Madison, 2009. Available at MINDS@UW.

[41]   Larry J. Stockmeyer: On approximation algorithms for #P. SIAM J. Comput., 14(4):849–861, 1985. [doi:10.1137/0214060]

[42]   Gregory Valiant and Paul Valiant: A CLT and tight lower bounds for estimating entropy. Electron. Colloq. on Comput. Complexity (ECCC), 2010. [ECCC:TR10-179]

[43]   Gregory Valiant and Paul Valiant: Estimating the unseen: A sublinear-sample canonical estimator of distributions. Electron. Colloq. on Comput. Complexity (ECCC), 2010. [ECCC:TR10-180]

[44]   Gregory Valiant and Paul Valiant: The power of linear estimators. In Proc. 52nd FOCS, pp. 403–412, October 2011. See also [42] and [43]. [doi:10.1109/FOCS.2011.81]

[45]   Gregory Valiant and Paul Valiant: An automatic inequality prover and instance optimal identity testing. SIAM J. Comput., 46(1):429–455, 2017. Preliminary version in FOCS’14. [doi:10.1137/151002526]

[46]   Paul Valiant: Testing symmetric properties of distributions. SIAM J. Comput., 40(6):1927–1968, 2011. Preliminary version in STOC’08. [doi:10.1137/080734066, ECCC:TR07-135]

[47]   Wikipedia: Yes, Virginia, there is a Santa Claus — Wikipedia, The Free Encyclopedia, 2017. https://en.wikipedia.org/w/index.php?title=Yes,_Virginia,_there_is_a_Santa_Claus&oldid=805832621 [Online; accessed 05-November-2017].