Testing Juntas and Junta Subclasses with Relative Error

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: {0,1}^n →{0,1}, by the ratio of |f^-1(1) 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). Chen et al. (SODA 2025) observed that the class of k-juntas is poly(2^k,1/ϵ)-query testable in the relative-error model, and asked whether poly(k,1/ϵ) queries is achievable. We answer this question affirmatively by giving a Õ(k/ϵ)-query algorithm, matching the optimal complexity achieved in the less challenging standard model. Moreover, as our main result, we show that any 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.