Testing that distributions are close
| Author(s) : | Warren D. Smith Ronitt Rubinfeld Lance Fortnow Tugkan Batu Patrick White, |
| Publisher : | N/A |
| Publication Date : | 2000 |
| ISSN : | N/A |
| Abstract : | Given two distributions over an n element set, we wish to check whether these distributions are statistically close by only sampling. We give a sublinear algorithm which uses O(n, |