2026-08-10T23:06:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5726 2024-03-06T10:36:56Z ddc:004 open_access

Testing Shape Restrictions of Discrete Distributions Canonne, Clément L. Diakonikolas, Ilias Gouleakis, Themis Rubinfeld, Ronitt property testing probability distributions statistics lower bounds We study the question of testing structured properties (classes) of discrete distributions. Specifically, given sample access to an arbitrary distribution D over [n] and a property P, the goal is to distinguish between D in P and l_{1}(D,P)>epsilon. We develop a general algorithm for this question, which applies to a large range of "shape-constrained" properties, including monotone, log-concave, t-modal, piecewise-polynomial, and Poisson Binomial distributions. Moreover, for all cases considered, our algorithm has near-optimal sample complexity with regard to the domain size and is computationally efficient. For most of these classes, we provide the first non-trivial tester in the literature. In addition, we also describe a generic method to prove lower bounds for this problem, and use it to show our upper bounds are nearly tight. Finally, we extend some of our techniques to tolerant testing, deriving nearly-tight upper and lower bounds for the corresponding questions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Clément L. Canonne and Ilias Diakonikolas and Themis Gouleakis and Ronitt Rubinfeld 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.25 urn:nbn:de:0030-drops-57260 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.25 eng https://creativecommons.org/licenses/by/3.0/legalcode