Testing of Index-Invariant Properties in the Huge Object Model

by Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

Oded's comments

This is an obvious choice for me, since it refers to a research direction started in a work of Dana and me (see the second paragraph of the abstract below). The class of properties studied in the current work (see the third paragraph of the abstract) is very natural; opinion may vary if it is more or less natural than the class of label-invariant properties, but for sure it is in the same ballpark. I find the results described in the fourth paragraph of the abstract very interesting.

Unfortunately, the overviews (of the proofs) provided in Section 2 are not very insightful (or clear). For example, the key observation that underlies the quadratic emulation of adaptive testers by non-adaptive ones is that the actual adaptivity amounts to which sample to query but not in which location to query it, since we are considering index-invariant distributions and so may consider a random permutation of the sample queried. The (almost) tightness of this emulation is shown by using a property that supports indirect addressing, which is a mechanism available to an adaptive tester but not to a non-adaptive one. More specifically, the property is obtained by random permutations of a base property, whereas the relevant part of this permutation can be revealed by reading one sample. Knowing this permuation allows to emulate a tester of low query complexity for the base property, but non-adaptive testers must read a large portion of each sample in order to make good use of it (and so their query complexity is the product of the length of the samples and the sample complexity of the base property). As for the base property it combines a label-invariant property that has high sample complexity with a complex randomized encoding scheme that appeared in prior work.

The original abstract

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, and in various real-life statistical tasks.

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 essentially 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 in the case of index-invariant properties. This is in contrast with the tight (easily provable) exponential gap between adaptive and non-adaptive testers 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.

Available from ECCC TR22-155.

Back to list of Oded's choices.