A Lower Bound on the Complexity of Testing Grained Distributions

Webpage for a paper by Oded Goldreich and Dana Ron


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.

Material available on-line

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