Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-012 | 9th February 2012 20:26

On the Effect of the Proximity Parameter on Property Testers

RSS-Feed




TR12-012
Authors: Oded Goldreich
Publication: 9th February 2012 20:26
Downloads: 2739
Keywords: 


Abstract:

This note refers to the effect of the proximity parameter on the operation of (standard) property testers. Its bottom-line is that, except in pathological cases, the effect of the proximity parameter is restricted to determining the query complexity of the tester. The point is that, in non-pathological cases, the mapping of the
proximity parameter to the query complexity can be reversed in an adequate manner.



ISSN 1433-8092 | Imprint