Volume 2 (2006)
Article 9 pp. 173-183
Tolerant Versus Intolerant Testing for Boolean Properties
Received: April 3, 2006
Published: September 25, 2006
Published: September 25, 2006
Keywords: property testing, tolerant testing, PCP of proximity
Categories: short, complexity theory, query complexity, property testing, lower bounds, probabilistically checkable proofs, PCP
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 (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.

Licensed under a Creative Commons License