Projects per year
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.
|Title of host publication||Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms|
|Number of pages||14|
|Publication status||Published - 2015|
FingerprintDive into the research topics of 'Testing Identity of Structured Distributions'. Together they form a unique fingerprint.
- 1 Finished
1/09/14 → 31/08/15