Two-Sided Error Proximity Oblivious Testing
Webpage for a paper by Oded Goldreich and Igor Shinkar
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 $\e$-far from having
the property are accepted with probability at most $c-F(\e)$,
where $F:(0,1]\to(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\in(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.
Material available on-line
Back to
either Oded Goldreich's homepage.
or general list of papers.