Classes Testable with $O(1/ε)$ Queries for Small $ε$ Independent of the Number of Variables
This provides efficient testing algorithms for specific Boolean function classes, which is incremental but extends prior results to more classes.
The paper tackles the problem of testing Boolean function classes with query complexity independent of the number of variables, showing that classes like k-junta and sparse polynomials are testable with O(1/ε) queries for small ε, matching the known lower bound of Ω(1/ε).
In this paper, we study classes of Boolean functions that are testable with $O(Ï+1/ε)$ queries, where $Ï$ 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 $ε\le 1/Ï$, the query complexity is $O(1/ε)$, matching the known tight bound $Ω(1/ε)$. 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/ε)$ queries for $ε<1/Ï$, where $Ï$ depends on $k$ and independent of the total number of variables $n$.