Trading query complexity for sample-based testing and multi-testing scalability

by Eldar Fischer, Oded Lachish, and Yadu Vadusev

Oded's comments

The presentation of the context is slightly inaccurate. Firstly, POTs were defined in GR08 as being potentially adaptive and the transformation (from POTs to sample-based testers) in GR13 refers also to adaptive POTs. Hence, Thm 1.1 in the current paper is actually incomparable to the said result in GR13: On the one hand, Thm 1.1 gets rid of the ``almost uniform'' requirement in GR13; but, on the other hand, Thm 1.1 applies only to non-adaptive POTs and yields a weaker bound.

The difference between adaptive and non-adaptive POTs is not very significant when the alphabet size is a constant (and the number of queries is a constant), but Thm 1.1 refers also to growing alphabet. In particular, Thm 1.1 complements a negative result in GR13, which establish the necessirty of the ``almost uniform'' requirement for transforming POTs to sample-based testers, by showing that the huge alphabet used in that negative result (of GR13) was indeed inherent. Here it is important to note that the negative result in GR13 also referred to a constant-query non-adaptive POT (of one-sided error). Thm 1.1 shows that, in such a case, such POTs (reagrdless of the ``almost uniform'' requirement) yield sample-based testers with a number of samples that is linear in the logarithm of the alphabet size.

I want to call attention to the new notion of multitests, which refers to oracle machines that test the given input for several properties. The point, of course, is to achieve this within complexity that is lower than the obvious solution of running adequate tests independently for each of the properties. Indeed, a sample-based tester is suitable towards this purpose; in fact, a tester that is canonical for a class of properties that contains all properties of interest suffices, where a test (or rather a testing schema) is canoniacl for a class if it uses the same query distruibution for each property in the class (and only its decision predicate depends on the specific property being tested). Canonical testers were considered [HERE] in the context of testing graph properties (in the dense graph model), but as far as I recall such a general notion of canonical testing has not appeared before.

Beware: The exponsition is quite challenging to the reader.

The original abstract

We show here that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than $1$, power of $n$. Since the query distribution of the sample-based algorithm is not dependent at all on the property, or the original algorithm, this has many implications in scenarios where there are many properties that need to be tested for concurrently, such as testing (relatively large) unions of properties, or converting a Merlin-Arthur Proximity proof (as per [Gur and Rothblum, 2013]) to a proper testing algorithm.

The proof method involves preparing the original testing algorithm for a combinatorial analysis, which in turn involves a new result about the existence of combinatorial structures (essentially generalized sunflowers) that allow the sample-based tester to replace the original constant query complexity tester.

See ECCC TR15-089.

Back to list of Oded's choices.