Testing Identity of Structured Distributions

Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin

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


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
Number of pages14
ISBN (Electronic)978-1-61197-373-0
ISBN (Print)978-1-61197-374-7
Publication statusPublished - 2015


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

Cite this