Authors
Oded Goldreich
Publication date
2017/9/6
Description
The collision probability tester, introduced by Goldreich and Ron (ECCC, TR00-020, 2000), distinguishes the uniform distribution over [n] from any distribution that is ǫ-far from this distribution using poly (1/ǫ)·
√ n samples. While the original analysis established only an upper bound of O (1/ǫ) 4·√ n on the sample complexity, a recent analysis of Diakonikolas, Gouleakis,
Scholar articles