## A Lower Bound on the Complexity of Testing Grained Distributions

#### Webpage for a paper by Oded Goldreich and Dana Ron

#### Abstract

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.