Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability

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 [Gold Reich 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. For the analysis we develop a structural lemma for hyper graphs that may be of independent interest. When analyzing a hyper graph that was extracted from a 2-sided test, it allows for finding generalized sunflowers that provide for a large-deviation type analysis. For 1-sided tests the bounds can be improved further by applying Janson's inequality directly over our structures.

Authors

• Eldar Fischer
• Oded Lachish
• Yadu Vasudev

Keywords

• Testing
• Computer science
• Complexity theory
• Scalability
• Algorithm design and analysis
• Indexes
• Polynomials
• Query Complexity
• Sunflower
• Original Algorithm
• Testing Algorithm
• Original Test
• 2-sided Test
• High Probability
• Version Of Test
• Distribution Test
• Family Settings
• Disjoint Sets
• Query Set
• Vertex Degree
• Sparse Graph
• Support Of Distribution
• Alphabet Size
• property testing
• sampling
• hypergraphs