Let's Try and Be More Tolerant: On Tolerant Property Testing and Distance ApproximationA property testing algorithm is required to accept objects that have a prespecified property P and reject those that are relatively far from having P. To this end, it is given query (or sampling) access to the object, and is allowed a small failure probability. Its query/sample complexity is required ...
