The uniform distribution is complete with respect to testing identity to a fixed distribution

Webpage for a paper by Oded Goldreich


Inspired by Diakonikolas and Kane (2016), we reduce the class of problems consisting of testing whenther an unknown distribution over $[n]$ equals a fixed distribution to this very problem when the fixed distribution is uniform over $[n]$. Our reduction preserves the parameters of the problem, which are $n$ and the proximity parameter $\e>0$, up to a constant factor. While this reduction yields no new bounds on the sample complexity of either problems, it provides a simple way of obtaining testers for equality to arbitrary fixed distributions from testers for the uniform distribution.

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.