Trading query complexity for sample-based testing
This week the colloquium will be given by Prof. Eldar Fischer from Israel Institute of Technology (the Technion)
Title: Trading query complexity for sample-based testing
A property testing algorithm is one that makes as few queries as possible from an input with n bits (larger size alphabets can also be considered), and distinguishes with high probability between the case where the input satisfies a given property, and the case where even changing up to an epsilon portion of the bits will not yield an input satisfying the property.
The best possible testing algorithms are those whose number of queries depends only on epsilon and not on n. Another useful feature of a tester is how "predictable" is the way it chooses its queries. If the query choices are not dependent on the particular property (and only the output choice is), then we can for example test for many properties at once using the same query set.
The most "oblivious" testers are sample-based testers as defined by Goldreich and Ron. Such tests completely ignore the structure of the input, and just decide for every input bit in itself whether to read it based on a (biased) coin toss. Such algorithms cannot have a constant number of queries, and a good situation is having each bit selected with a probability that is some negative power of n, meaning that the average number of queries made would be some power of n that is smaller than 1.
In this work we show how to convert any tester with a constant number of queries (depending only on the approximation parameter epsilon) to a sample-based tester whose probability is a negative power of n, and with good parameters for non-adaptive tests. Additionally, if the original tester had a 1-sided error, so will the sample-based one.
For this conversion to happen we show a way to treat a non-adaptive testing algorithm as little more than a uniform hypergraph. We then use a combinatorial lemma that may be interesting in its own right, that finds in every hypergraph with a linear number of edges a "constellation", that is, a subset of the edges with good ("average-like") guarantees on all its degrees outside a relatively small set of "core vertices".
Joint work with Oded Lachish and Yadu Vasudev.