Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Universal:
TR15-089 | 31st May 2015
Eldar Fischer, Oded Lachish, Yadu Vadusev

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

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 ... more >>>

ISSN 1433-8092 | Imprint