Published: September 25, 2006
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, 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, but 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., we exhibit a property which has constant query intolerant testers but for which any tolerant tester requires $n^{\Omega(1)}$ queries.
Licensed under a Creative Commons License