Name
Abstract | ||
|---|---|---|
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 |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1002/rsa.20582 | Random Structures and Algorithms |
Keywords | Field | DocType |
property testing,graph properties | Boolean function,Discrete mathematics,Combinatorics,Property testing,Graph property,struct,Regular graph,Mathematics | Journal |
Volume | Issue | ISSN |
48 | 2 | 1042-9832 |
Citations | PageRank | References |
3 | 0.41 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oded Goldreich | 1 | 12376 | 2035.01 |
| Igor Shinkar | 2 | 24 | 8.97 |