Testing Juntas and Junta Subclasses with Relative Error.
X. Chen and W. Pires and T. Pitassi and R. Servedio.
In Conference on Learning Theory (COLT), 2025, to appear.


Abstract:

This paper considers the junta testing problem in a recently introduced ``relative error'' variant of the standard Boolean function property testing model. In relative-error testing we measure the distance from $f$ to $g$, where $f,g: \zo^n \to \zo$, by the ratio of $|f^{-1}(1) \triangle g^{-1}(1)|$ (the number of inputs on which $f$ and $g$ disagree) to $|f^{-1}(1)|$ (the number of satisfying assignments of $f$), and we give the testing algorithm both black-box access to $f$ and also access to independent uniform samples from $f^{-1}(1)$.

\cite{CDHLNSY2024} observed that the class of $k$-juntas is $\poly(2^k,1/\eps)$-query testable in the relative-error model, and asked whether $\poly(k,1/\eps)$ queries is achievable. We answer this question affirmatively by giving a $\tilde{O}(k/\eps)$-query algorithm, matching the optimal complexity achieved in the less challenging standard model. Moreover, as our main result, we show that any \emph{subclass} of $k$-juntas that is closed under permuting variables is relative-error testable with a similar complexity. This gives highly efficient relative-error testing algorithms for a number of well-studied function classes, including size-$k$ decision trees, size-$k$ branching programs, and size-$k$ Boolean formulas.

Link to full version


Back to main papers page