Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-129 | 6th September 2021 15:24

A Lower Bound on the Complexity of Testing Grained Distributions

RSS-Feed




TR21-129
Authors: Oded Goldreich, Dana Ron
Publication: 6th September 2021 15:24
Downloads: 487
Keywords: 


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.



ISSN 1433-8092 | Imprint