ECCC-Report TR22-013https://eccc.weizmann.ac.il/report/2022/013Comments and Revisions published for TR22-013en-usSat, 05 Feb 2022 18:37:06 +0200
Paper TR22-013
| On properties that are non-trivial to test |
Nader Bshouty,
Oded Goldreich
https://eccc.weizmann.ac.il/report/2022/013In 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. Sat, 05 Feb 2022 18:37:06 +0200https://eccc.weizmann.ac.il/report/2022/013