Two‐sided error proximity oblivious testing1. Issue 2 (24th December 2014)

• Record Type: Journal Article
• Authors: Goldreich, Oded; Shinkar, Igor
• Is Part Of: Random structures & algorithms. Volume 48:Issue 2(2016)
• Page Start: 341
• Page End: 383
• Publication Date: 2014-12-24
• Subjects: property testing -- proximity‐oblivious testers -- one‐sided vs two‐sided error probability -- graph properties -- testing properties of distributions; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20582
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Loosely speaking, a proximity‐oblivious (property) tester is a randomized algorithm that makes a constant number of queries to a tested object and distinguishes objects that have a predetermined property from those that lack it. Specifically, for some threshold probability c, objects having the property are accepted with probability at least c, whereas objects that are ϵ ‐far from having the property are accepted with probability at most c − F ( ϵ ), where F : (0, 1] → (0, 1] is some fixed monotone function. (We stress that, in contrast to standard testers, a proximity‐oblivious tester is not given the proximity parameter.) The foregoing notion, introduced by Goldreich and Ron (STOC 2009), was originally defined with respect to c = 1, which corresponds to one‐sided error (proximity‐oblivious) testing. Here we study the two‐sided error version of proximity‐oblivious testers; that is, the (general) case of arbitrary c ∊ (0, 1]. We show that, in many natural cases, two‐sided error proximity‐oblivious testers are more powerful than one‐sided error proximity‐oblivious testers; that is, many natural properties that have no one‐sided error proximity‐oblivious testers do have a two‐sided error proximity‐oblivious tester. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 341–383, 2016