loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Eldar Fischer, Technion — Israel Institute of Technology
Lance Fortnow, University of Chicago
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.