Testing Distribution Identity Efficiently

Details Testing Distribution Identity Efficiently Testing Distribution Identity Efficiently

2009-10-16

arxiv.org/abs/0910.3243v1

Computer Science

Data Structures and Algorithms

4 pages

Scientific paper

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)).

Affiliated with

Also associated with

No associations

Rating

Testing Distribution Identity Efficiently does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Testing Distribution Identity Efficiently, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Testing Distribution Identity Efficiently will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-89399