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

Eldar Fischer, Oded Lachish, Yadu Vasudev

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 an…