Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-013 | 5th February 2022 18:36

On properties that are non-trivial to test

RSS-Feed




TR22-013
Authors: Nader Bshouty, Oded Goldreich
Publication: 5th February 2022 18:37
Downloads: 623
Keywords: 


Abstract:

In this note we show that all sets that are neither finite nor too dense are non-trivial to test in the sense that, for every \epsilon>0, distinguishing between strings in the set and strings that are \epsilon-far from the set requires \Omega(1/\epsilon) queries.
Specifically, we show that if, for infinitely many n's, the set contains at least one n-bit long string and at most 2^{n-\Omega(n)} many n-bit strings, then it is non-trivial to test.



ISSN 1433-8092 | Imprint