The study of distribution testing has become ubiquitous in the area of property testing, both for its theoretical appeal, as well as for its applications in other fields of Computer Science. The original distribution testing model relies on samples drawn independently from the distribution to be tested. However, when testing distributions over the $n$-dimensional Hamming cube $\left\{0,1\right\}^{n}$ for a large $n$, even reading a few samples is infeasible. To address this, Goldreich and Ron [ITCS 2022] have defined a model called the huge object model, in which the samples may only be queried in a few places. In this work, we initiate a study of a general class of properties in the huge object model, those that are invariant under a permutation of the indices of the vectors in $\left\{0,1\right\}^{n}$, while still not being necessarily fully symmetric as per the definition used in traditional distribution testing. We prove that every index-invariant property satisfying a bounded VC-dimension restriction admits a property tester with a number of queries independent of n. To complement this result, we argue that satisfying only index-invariance or only a VC-dimension bound is insufficient to guarantee a tester whose query complexity is independent of n. Moreover, we prove that the dependency of sample and query complexities of our tester on the VC-dimension is tight. As a second part of this work, we address the question of the number of queries required for non-adaptive testing. We show that it can be at most quadratic in the number of queries required for an adaptive tester of index-invariant properties. This is in contrast with the tight exponential gap for general non-index-invariant properties. Finally, we provide an index-invariant property for which the quadratic gap between adaptive and non-adaptive query complexities for testing is almost tight.
翻译:在财产测试领域,分配测试的研究已经变得无处不在,无论是它的理论吸引力,还是它在计算机科学其他领域的应用。原始分发测试模型依靠的是独立于要测试的分布模型的样本。然而,当对一大笔美元(left),甚至读取一些样本都无法做到。要解决这个问题,Goldreich和Ron[ITS 2022]已经定义了一个称为巨大对象模型的模式,其中样本只能在少数地方查询。在这项工作中,我们开始研究一个大对象模型中独立于要测试的普通属性类别。在美元(left),0,1\\rent}美元(right}美元)的矢量指数的变异性分布时,即使按照传统分配测试所使用的定义,也不一定完全具有对等性。我们证明,每个具有内嵌式的 VC 的变异性变异性标数只能在少数地方进行不精确的内置变异性测试。