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

<p>*(<em>for junta-ness, such a separation is shown only for non-adaptive testers.)</em></p>

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

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

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

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

<blockquote>
  <p><strong>Theorem 3</strong>. ([1]) Tolerant testing of unateness has query complexity $\tilde{\Omega}(n)$.</p>
</blockquote>

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

<hr>

<p>[1] Erik Waingarten and Amit Levi. <em>Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs</em>, 2018. <a href="https://arxiv.org/abs/1805.01074" rel="nofollow noreferrer">arXiv:1805.01074</a></p>

<p>[2] Eric Blais. <em>Improved Bounds for Testing Juntas.</em> APPROX-RANDOM, 2008.</p>

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

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

CC BY-SA 4.0
2018-05-04T18:00:02.360Z
2018-05-04T18:00:02.360Z
Clement C.
<p><em>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.</em></p>

<p>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:</p>

<ul>
<li><p>if $f\in \mathcal{P}$, then the algorithm returns $\textsf{accept}$ with probability at least $2/3$;</p></li>
<li><p>if $d(f,\mathcal{P}) &gt; \varepsilon$, then the algorithm returns $\textsf{reject}$ with probability at least $2/3$;</p></li>
</ul>

<p>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.</p>

<p><em>Tolerant</em> 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' &lt; \varepsilon$ is another input to the algorithm. In particular, tolerant testing is at least as hard as testing, by choosing $\varepsilon' = 0$.</p>

<p>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}$. <em>(Of course, here the word "natural" is fuzzily defined; I guess we recognize what it means when we see it.)</em></p>

<p>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.</p>

<blockquote>
  <p>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}$?</p>
</blockquote>

<hr>

<p>[1] <em>Tolerant Versus Intolerant Testing for Boolean Properties</em>, Eldar Fischer and Lance Fortnow. <em>Theory of Computing</em>, 2006. <a href="http://theoryofcomputing.org/articles/v002a009/" rel="nofollow noreferrer">http://theoryofcomputing.org/articles/v002a009/</a></p>

<reference-request><lower-bounds><property-testing>
Separations between testing and tolerant testing for (natural) classes of functions?
Clement C.
# Separations between testing and tolerant testing for (natural) classes of functions?

(Asked by: username_0 on 2018-01-21)

*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/>

**Tags:** reference-request, lower-bounds, property-testing


---

## 1 answers

### Answer by username_0 on 2018-05-04. Score: 0 | Accepted answer

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](https://arxiv.org/abs/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.


---

