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

Nader H. Bshouty, George Haddad

In this paper, we study classes of Boolean functions that are testable with $O(\psi +1/\epsilon )$ queries, where $\psi$ depends on the parameters of the class (e.g., the number of terms, the num…