ECCC-Report TR21-129https://eccc.weizmann.ac.il/report/2021/129Comments and Revisions published for TR21-129en-usMon, 06 Sep 2021 15:24:30 +0300
Paper TR21-129
| A Lower Bound on the Complexity of Testing Grained Distributions |
Oded Goldreich,
Dana Ron
https://eccc.weizmann.ac.il/report/2021/129A 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.
Mon, 06 Sep 2021 15:24:30 +0300https://eccc.weizmann.ac.il/report/2021/129