On the Effect of the Proximity Parameter on Property Testers

Webpage for a paper by Oded Goldreich


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.

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.