×

Two-sided error proximity oblivious testing. (English) Zbl 1352.68285

Summary: 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 \(\epsilon\)-far from having the property are accepted with probability at most \(c-F(\epsilon)\), 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 the first author and D. Ron [in: Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. New York, NY: Association for Computing Machinery (ACM). 141–150 (2009; Zbl 1304.05134)], 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.

MSC:

68W20 Randomized algorithms
05C85 Graph algorithms (graph-theoretic aspects)
68W25 Approximation algorithms

Citations:

Zbl 1304.05134
Full Text: DOI

References:

[1] N.Alon, E.Fischer, M.Krivelevich, and M.Szegedy, Efficient testing of large graphsCombinatorica20 (2000), 451-476. · Zbl 1052.68096
[2] J.Bochnak, M.Coste, and M.Roy, Real algebraic geometry, Volume 36 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics, Springer‐Verlag Berlin HeidelbergNew York, 1998. · Zbl 0912.14023
[3] O.Goldreich, S.Goldwasser, and D.Ron, Property testing and its connection to learning and approximation, J ACM45 (1998), 653-750. Extended abstract in 37th FOCS, 1996. · Zbl 1065.68575
[4] O.Goldreich and D.Ron, Property testing in bounded degree graphsAlgorithmica32 (2002), 302-343. Extended abstract in 29th STOC, 1997. · Zbl 0990.68103
[5] O.Goldreich and D.Ron, Algorithmic aspects of property testing in the dense graphs model SIAMJ Comput40 (2011), 376-445. Extended abstract in 13th RANDOM, LNCS 5687, 2009. · Zbl 1234.68137
[6] O.Goldreich and D.Ron, On proximity oblivious testing, SIAM J Comput40 (2011), 534-566. Extended abstract in 41st STOC, 2009. · Zbl 1223.68045
[7] O.Goldreich and I.Shinkar, Two‐sided error proximity oblivious testing ECCC, TR12‐021 (2012). (See Revision 4, 2014.), http://eccc.hpi-web.de/.
[8] O.Goldreich and L.Trevisan, Three theorems regarding testing graph properties, Random Struct Algor23 (2003), 23-57. · Zbl 1048.68062
[9] O.Goldreich and L.Trevisan, Errata to Three theorems regarding testing graph properties. Manuscript, August 2005, Available from http://www.wisdom.weizmann.ac.il/ oded/p_ttt.html
[10] D.Ron, Property testing: A learning theory perspective, Found Trends Mach Learn1 (2008), 307-402.
[11] D.Ron, Algorithmic and analysis techniques in property testing, Found Trends TCS5 (2009), 73-205. · Zbl 1184.68610
[12] R.Rubinfeld and M.Sudan, Robust characterization of polynomials with applications to program testing, SIAM J Comput25 (1996), 252-271. · Zbl 0844.68062
[13] P.Solernó, Effective Łojasiewicz inequalities in semialgebraic geometryAppl Algebra Eng Commun Comput2 (1990), 1-14. · Zbl 0754.14035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.