## On properties that are non-trivial to test

#### Webpage for a paper by Nader Bshouty and Oded Goldreich

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

#### Material available on-line

- First version posted:
Feb 2022.
- Revisions: none yet.

Back to
either Oded Goldreich's homepage
or general list of papers.