Testing Juntas and Junta Subclasses with Relative Error
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917984182730752 |
|---|---|
| author | Chen, Xi Pires, William Pitassi, Toniann Servedio, Rocco A. |
| author_facet | Chen, Xi Pires, William Pitassi, Toniann Servedio, Rocco A. |
| contents | This papers 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 $\text{poly}(2^k,1/ε)$-query testable in the relative-error model, and asked whether $\text{poly}(k,1/ε)$ queries is achievable. We answer this question affirmatively by giving a $\tilde{O}(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_09312 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Testing Juntas and Junta Subclasses with Relative Error Chen, Xi Pires, William Pitassi, Toniann Servedio, Rocco A. Computational Complexity Discrete Mathematics Data Structures and Algorithms This papers 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 $\text{poly}(2^k,1/ε)$-query testable in the relative-error model, and asked whether $\text{poly}(k,1/ε)$ queries is achievable. We answer this question affirmatively by giving a $\tilde{O}(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. |
| title | Testing Juntas and Junta Subclasses with Relative Error |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.09312 |