arXiv:2604.05615 · v2

Classes Testable with $O(1/ε)$ Queries for $ε$ Below an $n$-Independent Threshold

首次提交 2026-04-07 17:04

版本更新 2026-11-12 18:04

雷达观测 2026-11-13 14:15

摘要

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.), is independent of (or sublinear in) $1/ε$, and is independent of the total number of variables $n$. In particular, when $ε$ is sufficiently small so that $ε=O(1/ψ)$, the query complexity is $O(1/ε)$, matching the known tight lower bound $Ω(1/ε)$. In particular, if the structural parameters of the class are fixed and $ε=1/ω_n(1)$ (e.g., $1/\log n$), then the asymptotic query complexity is $O(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$.

作者备注：Appears in the Proceedings of the 52nd International Conference on Current Trends in Theory and Practice of Computer Science (Sofsem 2027)