20th Annual IEEE Conference on Computational Complexity (CCC'05) Tolerant Versus Intolerant Testing for Boolean Properties San Jose, CA June 11-June 15 ISBN: 0-7695-2364-1
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2005.30
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^Ω(1) queries.
Citation:
Eldar Fischer, Lance Fortnow, "Tolerant Versus Intolerant Testing for Boolean Properties," ccc, pp.135-140, 20th Annual IEEE Conference on Computational Complexity (CCC'05), 2005 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||