Theory of Computing
-------------------
Title     : Tolerant Versus Intolerant Testing for Boolean Properties
Authors   : Eldar Fischer and Lance Fortnow
Volume    : 2
Number    : 9
Pages     : 173-183
URL       : https://theoryofcomputing.org/articles/v002a009

Abstract
--------

A property tester with high probability accepts inputs satisfying
a given property and rejects inputs that are far from satisfying
it. A tolerant property tester, as defined by Parnas, Ron, and
Rubinfeld (2004), must also accept inputs that are close enough to
satisfying the property. We construct two properties of binary
functions for which there exists a test making a constant number
of queries, yet there exists no such tolerant test. The first
construction uses Hadamard codes and long codes. Then, using
Probabilistically Checkable Proofs of Proximity as constructed by
Ben-Sasson et al. (2004), we exhibit a property which has constant
query intolerant testers but for which any tolerant tester
requires  n^{\Omega(1)}  queries.