Received: April 3, 2006
Published: September 25, 2006
DOI: 10.4086/toc.2006.v002a009
Abstract: [Plain Text Version]
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Ω(1) queries.