论文标题
测试巨大对象的分布
Testing Distributions of Huge Objects
论文作者
论文摘要
我们启动了一种新的属性测试模型的研究，该模型是分布和测试属性的测试属性的混合体。具体而言，新模型是指分布的测试属性，但这些是对巨大对象（即非常长的字符串）的分布。因此，该模型说明了这些对象中的局部探针总数（分别，对字符串的查询）以及对象之间的距离（分别，字符串），分布之间的距离定义为相对于字符串之间的相对锤击距离的地球移动距离的距离。 我们研究了该新模型中测试的查询复杂性，重点是三个方向。首先，我们尝试将新模型中测试属性的查询复杂性与标准分布测试模型中测试这些属性的样本复杂性相关联。其次，我们考虑了在新模型中自然产生的测试属性的复杂性（例如，捕获固定字符串随机变化的分布）。第三，我们考虑了在标准分布测试模型中广泛研究的测试属性的复杂性：两种情况是统一的分布和成对相同的分布。
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.
