Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-105 | 19th November 2004 00:00

Tolerant Versus Intolerant Testing for Boolean Properties


Authors: Eldar Fischer, Lance Fortnow
Publication: 25th November 2004 10:42
Downloads: 2896


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 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^c queries for some c>0.

ISSN 1433-8092 | Imprint