Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-032 | 10th March 2016 09:48

A Note on Tolerant Testing with One-Sided Error

RSS-Feed




TR16-032
Authors: Roei Tell
Publication: 10th March 2016 09:55
Downloads: 1279
Keywords: 


Abstract:

A tolerant tester with one-sided error for a property is a tester that accepts every input that is close to the property, with probability 1, and rejects every input that is far from the property, with positive probability. In this note we show that such testers require a linear number of queries.



ISSN 1433-8092 | Imprint