A lower bound on the complexity of testing grained distributions. (English) Zbl 07773324
Summary: For a natural number \(m\), a distribution is called \(m\)-grained, if each element appears with probability that is an integer multiple of \(1/m\). We prove that, for any constant \(c<1\), testing whether a distribution over \([\Theta (m)]\) is \(m\)-grained requires \(\Omega (m^c)\) samples, where testing a property of distributions means distinguishing between distributions that have the property and distributions that are far (in total variation distance) from any distribution that has the property.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Tugkan Batu (2001).Testing properties of distributions.Ph.D. thesis, Computer Science department, Cornell University. |
| [2] | Tugkan Batu & Clément L. Canonne (2017).Generalized Uniformity Testing. In Proceedings of the Fiftieth-Eighth Annual Symposium on Foundations of Computer Science (FOCS), 880-889. |
| [3] | Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld & Patrick White (2001). Testing Random Variables for Independence and Identity. In Proceedings of the Forty-Second Annual Symposium on Foundations of Computer Science (FOCS), 442-451. |
| [4] | Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith & Patrick White (2000). Testing that distributions are close. In Proceedings of the Forty-First Annual Symposium on Foundations of Computer Science (FOCS), 259-269. ISSN 0272-5428. The journal version of this paper appeared as ?. · Zbl 1281.68227 |
| [5] | Oded Goldreich (2016). The Uniform Distribution is Complete with respect to Testing Identity to a Fixed Distribution. Technical Report TR15-015, Electronic Colloquium on Computational Complexity (ECCC). · Zbl 07578387 |
| [6] | Oded Goldreich (2017). Introduction to Property Testing. Cambridge University Press. · Zbl 06797790 |
| [7] | Oded Goldreich, Shafi Goldwasser & Dana Ron (1998). Property testing and its connections to learning and approximation. Journal of the ACM 45, 653-750. · Zbl 1065.68575 |
| [8] | Sofya Raskhodnikova, Dana Ron, Amir Shpilka & Adam Smith (2009). Strong lower bonds for approximating distributions support size and the distinct elements problem. SIAM Journal on Computing 39(3), 813-842. · Zbl 1194.68124 |
| [9] | Steven Roman (2005). Advanced Linear Algebra. Springer. Graduate Texts in Mathematics, Vol. 135. · Zbl 1085.15001 |
| [10] | Gregory Valiant & Paul Valiant (2017). Estimating the Unseen: Improved Estimators for Entropy and Other Properties. Journal of the ACM 64(6). · Zbl 1426.62107 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
