A basic lower bound for property testing
<|reference_start|>A basic lower bound for property testing: An $\epsilon$-test for any non-trivial property (one for which there are both satisfying inputs and inputs of large distance from the property) should use a number of queries that is at least inversely proportional in $\epsilon$. However, to the best of our knowledge there is no reference proof for this intuition. Such a proof is provided here. It is written so as to not require any prior knowledge of the related literature, and in particular does not use Yao's method.<|reference_end|>
@article{fischer2024a,
    title={A basic lower bound for property testing},
    author={Eldar Fischer},
    journal={arXiv preprint arXiv:2403.04999},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.04999},
    primaryClass={cs.DS}
}