Classes Testable with $O(1/ε)$ Queries for Small $ε$ Independent of the Number of Variables
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913009992990720 |
|---|---|
| author | Bshouty, Nader H. Haddad, George |
| author_facet | Bshouty, Nader H. Haddad, George |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_05615 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Classes Testable with $O(1/ε)$ Queries for Small $ε$ Independent of the Number of Variables Bshouty, Nader H. Haddad, George Data Structures and Algorithms 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$. |
| title | Classes Testable with $O(1/ε)$ Queries for Small $ε$ Independent of the Number of Variables |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.05615 |