%0 Journal Article
%T Testing Distribution Identity Efficiently
%A Krzysztof Onak
%J Computer Science
%D 2009
%I arXiv
%X We consider the problem of testing distribution identity. Given a sequence of independent samples from an unknown distribution on a domain of size n, the goal is to check if the unknown distribution approximately equals a known distribution on the same domain. While Batu, Fortnow, Fischer, Kumar, Rubinfeld, and White (FOCS 2001) proved that the sample complexity of the problem is O~(sqrt(n) * poly(1/epsilon)), the running time of their tester is much higher: O(n) + O~(sqrt(n) * poly(1/epsilon)). We modify their tester to achieve a running time of O~(sqrt(n) * poly(1/epsilon)).
%U http://arxiv.org/abs/0910.3243v1