ECCC-Report TR12-021https://eccc.weizmann.ac.il/report/2012/021Comments and Revisions published for TR12-021en-usSun, 26 Jan 2014 19:47:05 +0200
Revision 4
| Two-Sided Error Proximity Oblivious Testing |
Oded Goldreich,
Igor Shinkar
https://eccc.weizmann.ac.il/report/2012/021#revision4Loosely 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.
Sun, 26 Jan 2014 19:47:05 +0200https://eccc.weizmann.ac.il/report/2012/021#revision4
Revision 3
| Two-Sided Error Proximity Oblivious Testing |
Oded Goldreich,
Igor Shinkar
https://eccc.weizmann.ac.il/report/2012/021#revision3Loosely 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.
Mon, 11 Jun 2012 18:22:51 +0300https://eccc.weizmann.ac.il/report/2012/021#revision3
Revision 2
| Two-Sided Error Proximity Oblivious Testing |
Oded Goldreich,
Igor Shinkar
https://eccc.weizmann.ac.il/report/2012/021#revision2Loosely 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.
Mon, 02 Apr 2012 20:08:39 +0300https://eccc.weizmann.ac.il/report/2012/021#revision2
Revision 1
| Two-Sided Error Proximity Oblivious Testing |
Oded Goldreich,
Igor Shinkar
https://eccc.weizmann.ac.il/report/2012/021#revision1Loosely 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.
Wed, 14 Mar 2012 20:10:09 +0200https://eccc.weizmann.ac.il/report/2012/021#revision1
Paper TR12-021
| Two-Sided Error Proximity Oblivious Testing |
Oded Goldreich,
Igor Shinkar
https://eccc.weizmann.ac.il/report/2012/021Loosely 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.
Wed, 14 Mar 2012 19:57:05 +0200https://eccc.weizmann.ac.il/report/2012/021