Volume 2 (2006) Article 9 pp. 173-183
Tolerant Versus Intolerant Testing for Boolean Properties
by
Received: April 3, 2006
Published: September 25, 2006
Download article from ToC site:
[PDF (156K)]    [PS (278K)]    [PS.GZ (71K)]
[Source ZIP]
Keywords: property testing, tolerant testing, PCP of proximity
ACM Classification: G.3, F.2.2
AMS Classification: 68Q99, 68W20

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.