# Separations between testing and tolerant testing for (natural) classes of functions?

Note: I am considering here property testing in the query model, with regard to Hamming distance. (So, for instance, of Boolean functions—I'm phrasing it that way below.) I am in particular not interested in separations in distribution testing.

The property testing model (for Boolean functions) asks for algorithms that, for a fixed property $\mathcal{P}\subseteq 2^{2^n}$, are provided with a proximity parameter $\varepsilon \in (0,1)$ and query access to an arbitrary function $f\colon \{0,1\}^n \to \{0,1\}$, return either $\textsf{accept}$ or $\textsf{reject}$, such that:

• if $f\in \mathcal{P}$, then the algorithm returns $\textsf{accept}$ with probability at least $2/3$;

• if $d(f,\mathcal{P}) > \varepsilon$, then the algorithm returns $\textsf{reject}$ with probability at least $2/3$;

where $d(f,\mathcal{P}) \stackrel{\rm def}{=} \inf_{g\in \mathcal{P}} d_H(f,g)$ is the minimum (Hamming) distance between $f$ and a function satisfying the property.

Tolerant testing (as introduced by Parnas, Ron, and Rubinfeld) relaxes the first (completeness) guarantee from $d(f,\mathcal{P}) = 0$ to $d(f,\mathcal{P})\leq \varepsilon'$, where $0\leq \epsilon' < \varepsilon$ is another input to the algorithm. In particular, tolerant testing is at least as hard as testing, by choosing $\varepsilon' = 0$.

However, I am aware of only very few separations between testing and tolerant testing which show the latter to be actually harder, for "natural" properties of functions $\mathcal{P}$. (Of course, here the word "natural" is fuzzily defined; I guess we recognize what it means when we see it.)

An example (for contrived properties) was given by Fischer and Fortnow [1], where they provide a property with $O_{\varepsilon,\varepsilon'}(1)$-query testers, while every tolerant tester requires $n^{\Omega(1)}$ queries. This is the extent of my knowledge regarding published or available results.

Is there any such separation known for an (arguably) natural property of Boolean functions? If not, of functions $f\colon \{0,1\}^n \to \mathbb{R}$, or $f\colon [n]^d \to \mathbb{R}$?

[1] Tolerant Versus Intolerant Testing for Boolean Properties, Eldar Fischer and Lance Fortnow. Theory of Computing, 2006. http://theoryofcomputing.org/articles/v002a009/

The recent preprint of A. Levi and E. Waingarten [1] establishes such a separation* for two "(arguably) natural" properties of functions: unateness and junta-ness.

*(for junta-ness, such a separation is shown only for non-adaptive testers.)

Theorem 1. ([1]) Non-adaptive tolerant testing of $k$-junta-ness has query complexity $\tilde{\Omega}(k^2)$.

On the other hand, Blais [2] showed that non-adaptive testing of $k$-juntas had query complexity $\tilde{O}(k^{3/2})$, hence the separation.

Theorem 2. ([1]) Non-adaptive tolerant testing of unateness has query complexity $\tilde{\Omega}(n^{3/2})$.

On the other hand, Baleshzar et al. [3] showed that non-adaptive testing of unateness had query complexity $\tilde{O}(n)$, hence the separation.

Theorem 3. ([1]) Tolerant testing of unateness has query complexity $\tilde{\Omega}(n)$.

On the other hand, Chen, Waingarten, and Xie [4] showed that non-adaptive testing of unateness had query complexity $\tilde{O}(n^{3/4})$, hence the separation.

[1] Erik Waingarten and Amit Levi. Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs, 2018. arXiv:1805.01074

[2] Eric Blais. Improved Bounds for Testing Juntas. APPROX-RANDOM, 2008.

[3] Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri. Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. ICALP, 2017.

[4] Xi Chen, Erik Waingarten, Jinyu Xie. Boolean Unateness Testing with $\tilde{O}(n^{3/4})$ Adaptive Queries. FOCS, 2017.