Testing Identity of Structured Distributions

Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin

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

Abstract

We study the question of identity testing for structured distributions. More precisely, given samples from a structured distribution q over [n] and an explicit distribution p over [n], we wish to distinguish whether q = p versus q is at least ε-far from p, in L1 distance. In this work, we present a unified approach that yields new, simple testers, with sample complexity that is information-theoretically optimal, for broad classes of structured distributions, including t-flat distributions, t-modal distributions, log-concave distributions, monotone hazard rate (MHR) distributions, and mixtures thereof.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherSIAM
Pages1841-1854
Number of pages14
ISBN (Electronic)978-1-61197-373-0
ISBN (Print)978-1-61197-374-7
DOIs
Publication statusPublished - 2015

Fingerprint

Dive into the research topics of 'Testing Identity of Structured Distributions'. Together they form a unique fingerprint.

Cite this