Projects per year
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 L_{1} distance. In this work, we present a unified approach that yields new, simple testers, with sample complexity that is informationtheoretically optimal, for broad classes of structured distributions, including tflat distributions, tmodal distributions, logconcave distributions, monotone hazard rate (MHR) distributions, and mixtures thereof.
Original language  English 

Title of host publication  Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms 
Publisher  SIAM 
Pages  18411854 
Number of pages  14 
ISBN (Electronic)  9781611973730 
ISBN (Print)  9781611973747 
DOIs  
Publication status  Published  2015 
Fingerprint
Dive into the research topics of 'Testing Identity of Structured Distributions'. Together they form a unique fingerprint.Projects
 1 Finished

Sublinear Algorithms for Approximating Probability Distribution
Diakonikolas, I.
1/09/14 → 31/08/15
Project: Research