Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #4 to TR12-021 | 26th January 2014 19:47

Two-Sided Error Proximity Oblivious Testing

RSS-Feed




Revision #4
Authors: Oded Goldreich, Igor Shinkar
Accepted on: 26th January 2014 19:47
Downloads: 1437
Keywords: 


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.



Changes to previous version:

Mainly revising the introduction so to include a more elaborate account of the main results.


Revision #3 to TR12-021 | 11th June 2012 18:22

Two-Sided Error Proximity Oblivious Testing





Revision #3
Authors: Oded Goldreich, Igor Shinkar
Accepted on: 11th June 2012 18:22
Downloads: 2831
Keywords: 


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.



Changes to previous version:

Minor corrections.


Revision #2 to TR12-021 | 2nd April 2012 20:08

Two-Sided Error Proximity Oblivious Testing





Revision #2
Authors: Oded Goldreich, Igor Shinkar
Accepted on: 2nd April 2012 20:08
Downloads: 2391
Keywords: 


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.



Changes to previous version:

New material included in a new Sec 3.3.


Revision #1 to TR12-021 | 14th March 2012 20:10

Two-Sided Error Proximity Oblivious Testing





Revision #1
Authors: Oded Goldreich, Igor Shinkar
Accepted on: 14th March 2012 20:10
Downloads: 2896
Keywords: 


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.



Changes to previous version:

The 2nd author's name was omitted due to system fault. The PDF is identical to the original.


Paper:

TR12-021 | 14th March 2012 19:57

Two-Sided Error Proximity Oblivious Testing





TR12-021
Authors: Oded Goldreich, Igor Shinkar
Publication: 14th March 2012 19:57
Downloads: 3148
Keywords: 


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.



ISSN 1433-8092 | Imprint