Testing Juntas and Junta Subclasses with Relative Error

Xi Chen, William Pires, Toniann Pitassi, R. A. Servedio
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:5214-5245, 2025.

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 \to \{0,1\}$, 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)$. Chen et al. (SODA 2025) observed that the class of $k$-juntas is poly$(2^k,1/\epsilon)$-query testable in the relative-error model, and asked whether poly$(k,1/\epsilon)$ queries is achievable. We answer this question affirmatively by giving a $\tilde{O}(k/\epsilon)$-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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-chen25h, title = {Testing Juntas and Junta Subclasses with Relative Error}, author = {Chen, Xi and Pires, William and Pitassi, Toniann and Servedio, R. A.}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {5214--5245}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/chen25h/chen25h.pdf}, url = {https://proceedings.mlr.press/v291/chen25h.html}, 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 \to \{0,1\}$, 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)$. Chen et al. (SODA 2025) observed that the class of $k$-juntas is poly$(2^k,1/\epsilon)$-query testable in the relative-error model, and asked whether poly$(k,1/\epsilon)$ queries is achievable. We answer this question affirmatively by giving a $\tilde{O}(k/\epsilon)$-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.} }
Endnote
%0 Conference Paper %T Testing Juntas and Junta Subclasses with Relative Error %A Xi Chen %A William Pires %A Toniann Pitassi %A R. A. Servedio %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-chen25h %I PMLR %P 5214--5245 %U https://proceedings.mlr.press/v291/chen25h.html %V 291 %X 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 \to \{0,1\}$, 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)$. Chen et al. (SODA 2025) observed that the class of $k$-juntas is poly$(2^k,1/\epsilon)$-query testable in the relative-error model, and asked whether poly$(k,1/\epsilon)$ queries is achievable. We answer this question affirmatively by giving a $\tilde{O}(k/\epsilon)$-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.
APA
Chen, X., Pires, W., Pitassi, T. & Servedio, R.A.. (2025). Testing Juntas and Junta Subclasses with Relative Error. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:5214-5245 Available from https://proceedings.mlr.press/v291/chen25h.html.

Related Material