Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin

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

Abstract

We give a general unified method that can be used for L1 closeness testing of a wide range of univariate structured distribution families. More specifically, we design a sample optimal and computationally efficient algorithm for testing the equivalence of two unknown (potentially arbitrary) univariate distributions under the Ak-distance metric: Given sample access to distributions with density functions p, q : I → R, we want to distinguish between the cases that p = q and ∥p - q∥Ak ≥ ∈ with probability at least 2/3. We show that for any k ≥ 2, ∈ > 0, the optimal sample complexity of the Ak-closeness testing problem is Θ(max{k4/5/∈6/5, k1/2/∈2}). This is the first o(k) sample algorithm for this problem, and yields new, simple L1 closeness testers, in most cases with optimal sample complexity, for broad classes of structured distributions.
Original languageEnglish
Title of host publication2015 IEEE 56th Annual Symposium on Foundations of Computer Science
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages1183-1202
Number of pages20
ISBN (Electronic)978-1-4673-8191-8
DOIs
Publication statusPublished - 17 Dec 2015

Publication series

Name
ISSN (Print)0272-5428

Fingerprint

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

Cite this