Trading query complexity for sample-based testing and multi-testing scalability.
- Speaker: Oded Lachish, Birkbeck, University of London.
- Date: Wednesday, 30 September 2015 from 16:00 to 17:00
- Location: Room 151, Birkbeck Main Building
We show 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.
The proof method involves preparing the original testing algorithm for a combinatorial analysis. For the analysis we develop a structural lemma for hypergraphs that may be of independent interest. All the ideas will be conveyed at an intuitive level.