2016/09/21 by Eldar Fischer, Fischer, Eldar, Oded Lachish +3
Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Machine Learning and Data Classification
paper · pdf · doi:10.48550/arxiv.1609.06736
openalex publication_date 2016/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Distribution testing deals with what information can be deduced about an\nunknown distribution over 1,\…,n , where the algorithm is only allowed\nto obtain a relatively small number of independent samples from the\ndistribution. In the extended conditional sampling model, the algorithm is also\nallowed to obtain samples from the restriction of the original distribution on\nsubsets of 1,\…,n .\n In 2015, Canonne, Diakonikolas, Gouleakis and Rubinfeld unified several\nprevious results, and showed that for any property of distributions satisfying\na "decomposability" criterion, there exists an algorithm (in the basic model)\nthat can distinguish with high probability distributions satisfying the\nproperty from distributions that are far from it in the variation distance.\n We present here a more efficient yet simpler algorithm for the basic model,\nas well as very efficient algorithms for the conditional model, which until now\nwas not investigated under the umbrella of decomposable properties.\nAdditionally, we provide an algorithm for the conditional model that handles a\nmuch larger class of properties.\n Our core mechanism is a way of efficiently producing an interval-partition of\n 1,\…,n that satisfies a "fine-grain" quality. We show that with such\na partition at hand we can directly move forward with testing individual\nintervals, instead of first searching for the "correct" partition of\n 1,\…,n .\n