zbMATH — the first resource for mathematics

Testing probability distributions using conditional samples. (English) Zbl 1328.68293

68W20 Randomized algorithms
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI arXiv
[1] J. A. Adell and P. Jodra, Exact Kolmogorov and total variation distances between some familiar discrete distributions, J. Inequal. Appl., 2006 (2006), 64307. · Zbl 1090.60506
[2] T. Batu, S. Dasgupta, R. Kumar, and R. Rubinfeld, The complexity of approximating the entropy, SIAM J. Comput., 35 (2005), pp. 132–150. · Zbl 1087.94012
[3] T. Batu, E. Fischer, L. Fortnow, R. Kumar, R. Rubinfeld, and P. White, Testing random variables for independence and identity, in Proceedings of FOCS, 2001, pp. 442–451.
[4] T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White, Testing that distributions are close, in Proceedings of FOCS, 2000, pp. 189–197.
[5] T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White, Testing closeness of discrete distributions, 60 (2013). · Zbl 1281.68227
[6] T. Batu, R. Kumar, and R. Rubinfeld, Sublinear algorithms for testing monotone and unimodal distributions, in Proceedings of STOC, ACM, New York, 2004, pp. 381–390. · Zbl 1192.68345
[7] A. Bhattacharyya, E. Fischer, R. Rubinfeld, and P. Valiant, Testing monotonicity of distributions over general partial orders, in Proceedings of ITCS, 2011, pp. 239–252.
[8] C. L. Canonne, D. Ron, and R. A. Servedio, Testing equivalence between distributions using conditional samples, in Proceedings of SODA, SIAM, Philadelphia, 2014, pp. 1174–1192. · Zbl 1421.68183
[9] S. Chakraborty, E. Fischer, Y. Goldhirsh, and A. Matsliah, On the power of conditional samples in distribution testing, in Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS ’13, New York, 2013, ACM, New York, pp. 561–580. · Zbl 1362.68288
[10] S.-O. Chan, I. Diakonikolas, G. Valiant, and P. Valiant, Optimal algorithms for testing closeness of discrete distributions, in Proceedings of SODA, SIAM, Philadelphia, 2014, pp. 1193–1203. · Zbl 1421.68184
[11] C. Daskalakis, I. Diakonikolas, R. A. Servedio, G. Valiant, and P. Valiant, Testing \(k\)-modal distributions: Optimal algorithms via reductions, in Proceedings of SODA, SIAM, Philadelphia, 2013, pp. 1833–1852. · Zbl 1421.68187
[12] D. P. Dubhashi and A. Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge University Press, Cambridge, 2009. · Zbl 1213.60006
[13] E. Fischer, The art of uninformed decisions: A primer to property testing, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 75 (2001), pp. 97–126. · Zbl 1024.68045
[14] O. Goldreich, S. Goldwasser, and D. Ron, Property testing and its connection to learning and approximation, J. ACM, 45 (1998), pp. 653–750. · Zbl 1065.68575
[15] O. Goldreich and D. Ron, On Testing Expansion in Bounded-Degree Graphs, Technical report TR00-020, ECCC, 2000. · Zbl 1343.68302
[16] O. Goldreich, ed., Property Testing: Current Research and Surveys, Lecture Notes in Comput. Sci. 6390, Springer, New York, 2010. · Zbl 1197.68012
[17] P. Indyk, R. Levi, and R. Rubinfeld, Approximating and testing \(k\)-histogram distributions in sub-linear time, in Proceedings of PODS, 2012, pp. 15–22.
[18] S.-K. Ma, Calculation of entropy from data of motion, J. Stat. Phys., 26 (1981), pp. 221–240.
[19] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, 1995. · Zbl 0849.68039
[20] J. Neyman, On the two different aspects of the representative method: The method of stratified sampling and the method of purposive selection, J. Roy. Statist. Soc., 97 (1934), pp. 558–625. · Zbl 0010.07201
[21] L. Paninski, Estimating entropy on \(m\) bins given fewer than \(m\) samples, IEEE Trans. Inform. Theory, 50 (2004), pp. 2200–2203. · Zbl 1315.94025
[22] L. Paninski, A coincidence-based test for uniformity given very sparsely sampled discrete data, IEEE Trans. Inform. Theory, 54 (2008), pp. 4750–4755. · Zbl 1322.62082
[23] S. Raskhodnikova, D. Ron, A. Shpilka, and A. Smith, Strong lower bonds for approximating distributions support size and the distinct elements problem, SIAM J. Comput., 39 (2009), pp. 813–842. · Zbl 1194.68124
[24] L. Reyzin, Extractors and the Leftover Hash Lemma, http://www.cs.bu.edu/\string reyzin/teaching/s11cs937/notes-leo-1.pdf, 2011.
[25] D. Ron, Property Testing: A Learning Theory Perspective, Found. Trends Mach. Learn., 1 (2008), pp. 307–402.
[26] D. Ron, Algorithmic and analysis techniques in property testing, Found. Trends Theor. Comput. Sci., 5 (2010), pp. 73–205.
[27] R. Rubinfeld and R. A. Servedio, Testing monotone high-dimensional distributions, Random Structures Algorithms, 34 (2009), pp. 24–44. · Zbl 1165.62037
[28] R. Rubinfeld and M. Sudan, Robust characterization of polynomials with applications to program testing, SIAM J. Comput., 25 (1996), pp. 252–271. · Zbl 0844.68062
[29] G. Valiant and P. Valiant, A CLT and Tight Lower Bounds for Estimating Entropy, Technical report TR10-179, ECCC, 2010. · Zbl 1288.68186
[30] G. Valiant and P. Valiant, Estimating the Unseen: A Sublinear-Sample Canonical Estimator of Distributions, Technical report TR10-180, ECCC, 2010. · Zbl 1288.68186
[31] G. Valiant and P. Valiant, Estimating the unseen: An \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs, in Proceedings of STOC, 2011, pp. 685–694. · Zbl 1288.68186
[32] G. Valiant and P. Valiant, An automatic inequality prover and instance optimal identity testing, in Proceedings of FOCS, 2014, pp. 51–60. · Zbl 1362.62107
[33] P. Valiant, Testing symmetric properties of distributions, SIAM J. Comput., 40 (2011), pp. 1927–1968. · Zbl 1233.62112
[34] Wikipedia, Stratified Sampling, http://en.wikipedia.org/wiki/Stratified_sampling, (July 1, 2013).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.