# New Lower Bounds for Adaptive Tolerant Junta Testing

arXiv: https://arxiv.org/abs/2304.10647 · HTML: https://mlsanity.com/paper/2304.10647/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2023.

## Built on by (most cited first, 1 of 1)

- [Tolerant Algorithms for Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2406.02742/) (2024)

## Abstract (arXiv)

We prove a k-Omega(log(varepsilon2 - varepsilon1)) lower bound for adaptively testing whether a Boolean function is varepsilon1-close to or varepsilon2-far from k-juntas. Our results provide the first superpolynomial separation between tolerant and non-tolerant testing for a natural property of boolean functions under the adaptive setting. Furthermore, our techniques generalize to show that adaptively testing whether a function is varepsilon1-close to a k-junta or varepsilon2-far from (k + o(k))-juntas cannot be done with textsfpoly (k, (varepsilon2 - varepsilon1)-1) queries. This is in contrast to an algorithm by Iyer, Tal and Whitmeyer [CCC 2021] which uses textsfpoly (k, (varepsilon2 - varepsilon1)-1) queries to test whether a function is varepsilon1-close to a k-junta or varepsilon2-far from O(k/(varepsilon2-varepsilon1)2)-juntas.