3
$\begingroup$

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/

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.