Distribution testing has long been studied in the context of theoretical computer science and statistics. The classical model of distribution testing can be seen as too weak in practice, with even the simplest tasks requiring polynomial (though sublinear) sample complexity. We explore non-classical models tailored to cope with this model's infeasibility for distributions defined over very large data sets. We consider two kinds of models: models that are stronger than the classical one, in which testing can be done more efficiently, and a weaker model, which is better suited for extremely high-dimensional data sets.
The stronger model is the conditional sampling model, in which the algorithm can sample the input distribution when conditioned on subsets of the domain. We consider this model as well as a few of its restricted variants, such as the subcube conditional model. We tighten the bounds for a few core algorithmic tasks in these conditional models.
Finally, we explore the behavior of algorithms in the Huge Object model, which combines the classical distribution testing model with the string testing model to more realistically handle distributions over extremely high-dimensional data sets.