Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Probability distributions:
TR12-152 | 7th November 2012
Anindya De, Ilias Diakonikolas, Rocco Servedio

Inverse Problems in Approximate Uniform Generation

We initiate the study of \emph{inverse} problems in approximate uniform generation, focusing on uniform generation of satisfying assignments of various types of Boolean functions. In such an inverse problem, the algorithm is given uniform random satisfying assignments of an unknown function $f$ belonging to a class $\C$ of Boolean functions ... more >>>

TR14-021 | 18th February 2014
Clement Canonne, Ronitt Rubinfeld

Testing probability distributions underlying aggregated data

In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution $D$ over $[n]$. More precisely, we define both the dual and extended ... more >>>

TR15-063 | 15th April 2015
Clement Canonne

A Survey on Distribution Testing: Your Data is Big. But is it Blue?

Revisions: 1

The field of property testing originated in work on program checking, and has evolved into an established and very active research area. In this work, we survey the developments of one of its most recent and prolific offspring, distribution testing. This subfield, at the junction of property testing and Statistics, ... more >>>

TR17-075 | 29th April 2017
Clement Canonne, Ilias Diakonikolas, Alistair Stewart

Fourier-Based Testing for Families of Distributions

Revisions: 1

We study the general problem of testing whether an unknown discrete distribution belongs to a given family of distributions. More specifically, given a class of distributions $\mathcal{P}$ and sample access to an unknown distribution $\mathbf{P}$, we want to distinguish (with high probability) between the case that $\mathbf{P} \in \mathcal{P}$ and ... more >>>

ISSN 1433-8092 | Imprint