Classes Testable with $O(1\mathrm{/}\epsilon )$ Queries for Small $\epsilon$ Independent of the Number of Variables

In this paper, we study classes of Boolean functions that are testable with $O(\psi +1\mathrm{/}\epsilon )$ queries, where $\psi$ depends on the parameters of the class (e.g., the number of terms, the number of relevant variables, etc.) but not on the total number of variables $n$. In particular, when $\epsilon \le 1\mathrm{/}\psi$, the query complexity is $O(1\mathrm{/}\epsilon )$, matching the known tight bound $\mathrm{\Omega }(1\mathrm{/}\epsilon )$. This result was previously known for classes of terms of size at most $k$ and exclusive OR functions of at most $k$ variables. In this paper, we extend this list to include the classes: $k$-junta, functions with Fourier degree at most $d$, $s$-sparse polynomials of degree at most $d$, and $s$-sparse polynomials. Additionally, we show that for any class $C$ of Boolean functions that depend on at most $k$ variables, if $C$ is properly exactly learnable, then it is testable with $O(1\mathrm{/}\epsilon )$ queries for $\epsilon <1\mathrm{/}\psi$, where $\psi$ depends on $k$ and independent of the total number of variables $n$.