Optimal Algorithms for Testing Closeness of Discrete Distributions

Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, Paul Valiant

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study the question of closeness testing for two discrete distributions. More precisely, given samples from two distributions p and q over an n-element set, we wish to distinguish whether p = q versus p is at least ∊-far from q, in either ℓ1 or ℓ2 distance. Batu et al [BFR+00, BFR+13] gave the first sub-linear time algorithms for these problems, which matched the lower bounds of [Val11] up to a logarithmic factor in n, and a polynomial factor of ∊.In this work, we present simple testers for both the ℓ1 and ℓ2 settings, with sample complexity that is information-theoretically optimal, to constant factors, both in the dependence on n, and the dependence on ∊; for the ℓ1 testing problem we establish that the sample complexity is Θ(max{n2/3/∊4/3,n1/2/∊2}).
Original languageEnglish
Title of host publicationProceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
EditorsChandra Chekuri
PublisherSociety for Industrial and Applied Mathematics
Pages1193-1203
Number of pages11
ISBN (Electronic)978-1-61197-340-2
ISBN (Print)978-1-61197-338-9
DOIs
Publication statusPublished - 5 Jan 2014
EventTwenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms - Portland, United States
Duration: 5 Jan 20147 Jan 2014

Conference

ConferenceTwenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA 2015
Country/TerritoryUnited States
CityPortland
Period5/01/147/01/14

Fingerprint

Dive into the research topics of 'Optimal Algorithms for Testing Closeness of Discrete Distributions'. Together they form a unique fingerprint.

Cite this