Two‐sided error proximity oblivious testing

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 , 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