Tolerant versus intolerant testing for Boolean properties
Tolerant versus intolerant testing for Boolean properties
复制标题
布尔属性的容忍与不容忍测试
DOI：
10.4086/toc.2006.v002a009
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
L. Fortnow
中科院分区：
文献类型：
--
作者：
E. Fischer;L. Fortnow
具有较高概率的属性测试仪接受满足给定属性的输入，并拒绝远远不令人满意的输入。由Parnas，Ron和Rubinfeld定义的耐受性属性测试仪还必须接受足够接近以满足该属性的输入。我们构建了存在的两个二进制函数的属性，其中存在一个持续数量的查询，但没有这种耐受性测试。第一个施工使用Hadamard代码和长密码。然后，使用Ben-Sasson等人构建的近端可检查证明。 Al。，我们展示具有恒定查询不耐受测试仪的属性，但任何耐受测试仪都需要N/SUP/SPL OMEGA/（1）/查询。
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/sup /spl Omega/(1)/ queries.