| Summary: | We initiate a study of a new model of property testing that is a hybrid of
testing properties of distributions and testing properties of strings.
Specifically, the new model refers to testing properties of distributions, but
these are distributions over huge objects (i.e., very long strings).
Accordingly, the model accounts for the total number of local probes into these
objects (resp., queries to the strings) as well as for the distance between
objects (resp., strings), and the distance between distributions is defined as
the earth mover's distance with respect to the relative Hamming distance
between strings.
We study the query complexity of testing in this new model, focusing on three
directions. First, we try to relate the query complexity of testing properties
in the new model to the sample complexity of testing these properties in the
standard distribution testing model. Second, we consider the complexity of
testing properties that arise naturally in the new model (e.g., distributions
that capture random variations of fixed strings). Third, we consider the
complexity of testing properties that were extensively studied in the standard
distribution testing model: Two such cases are uniform distributions and pairs
of identical distributions.
|
|---|