×

Proximity oblivious testing and the role of invariances. (English) Zbl 1343.68300

Goldberg, Leslie Ann (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17–19, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22934-3/pbk). Lecture Notes in Computer Science 6845, 579-592 (2011).
Summary: We present a general notion of properties that are characterized by local conditions that are invariant under a sufficiently rich class of symmetries. Our framework generalizes two popular models of testing graph properties as well as the algebraic invariances studied by T. Kaufman and M. Sudan [in: Proceedings of the 40th annual ACM symposium on theory of computing, STOC 2008. New York, NY: Association for Computing Machinery (ACM). 403–412 (2008; Zbl 1231.68290)]. Our focus is on the case that the property is characterized by a constant number of local conditions and a rich set of invariances.
We show that, in the aforementioned models of testing graph properties, characterization by such invariant local conditions is closely related to proximity oblivious testing (as defined by O. Goldreich 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)]. In contrast to this relation, we show that, in general, characterization by invariant local conditions is neither necessary nor sufficient for proximity oblivious testing. Furthermore, we show that easy testability is not guaranteed even when the property is characterized by local conditions that are invariant under a 1-transitive group of permutations.
For the entire collection see [Zbl 1219.68018].

MSC:

68W20 Randomized algorithms
05C85 Graph algorithms (graph-theoretic aspects)
94B60 Other types of codes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N., Fischer, E., Newman, I., Shapira, A.: A Combinatorial Characterization of the Testable Graph Properties: It’s All About Regularity. In: 38th STOC, pp. 251–260 (2006) · Zbl 1301.05354
[2] Alon, N., Shapira, A.: A Characterization of Easily Testable Induced Subgraphs. Combinatorics Probability and Computing 15, 791–805 (2006) · Zbl 1318.68191 · doi:10.1017/S0963548306007759
[3] Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs and non-approximability – towards tight results. SIAM Journal on Computing 27(3), 804–915 (1998) · Zbl 0912.68041 · doi:10.1137/S0097539796302531
[4] Ben-Sasson, E., Maatouk, G., Shpilka, A., Sudan, M.: Symmetric LDPC codes are not necessarily locally testable. ECCC, TR10-199 (2010)
[5] Blum, M., Luby, M., Rubinfeld, R.: Self-Testing/Correcting with Applications to Numerical Problems. JCSS 47(3), 549–595 (1993) · Zbl 0795.68131
[6] Fischer, E., Lachish, O., Matsliah, A., Newman, I., Yahalom, O.: On the Query Complexity of Testing Orientations for Being Eulerian. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol. 5171, pp. 402–415. Springer, Heidelberg (2008) Full version available from, http://www.cs.technion.ac.il/ oyahalom · Zbl 1159.68471 · doi:10.1007/978-3-540-85363-3_32
[7] Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM, 653–750 (July 1998) · Zbl 1065.68575 · doi:10.1145/285055.285060
[8] Goldreich, O., Kaufman, T.: Proximity Oblivious Testing and the Role of Invariances. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. LNCS, vol. 6650, pp. 1–5. Springer, Heidelberg (2011) · Zbl 1343.68093 · doi:10.1007/978-3-642-22670-0_1
[9] Goldreich, O., Ron, D.: Property Testing in Bounded Degree Graphs. Algorithmica 32(2), 302–343 (2002) · Zbl 0990.68103 · doi:10.1007/s00453-001-0078-7
[10] Goldreich, O., Ron, D.: On Proximity Oblivious Testing. ECCC, TR08-041 (2008); Also in the Proceedings of the 41st STOC 2009
[11] Goldreich, O., Trevisan, L.: Three theorems regarding testing graph properties. Random Structures and Algorithms 23(1), 23–57 (2003) · Zbl 1048.68062 · doi:10.1002/rsa.10078
[12] Grigorescu, E., Kaufman, T., Sudan, M.: 2-Transitivity is Insufficient for Local Testability. In: 23rd CCC, pp. 259–267 (2008) · Zbl 1283.94130 · doi:10.1109/CCC.2008.31
[13] Kaufman, T., Sudan, M.: Sparse Random Linear Codes are Locally Testable and Decodable. In: The Proceedings of the 48th FOCS, pp. 590–600 (2007) · doi:10.1109/FOCS.2007.8
[14] Kaufman, T., Sudan, M.: Algebraic Property Testing: The Role of Invariances. In: 40th STOC, pp. 403–412 (2008) · Zbl 1231.68290
[15] Parnas, M., Ron, D., Samorodnitsky, A.: Testing basic boolean formulae. SIAM Journal on Discrete Math. 16(1), 20–46 (2002) · Zbl 1041.68050 · doi:10.1137/S0895480101407444
[16] Ron, D.: Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning 1(3), 307–402 (2008) · doi:10.1561/2200000004
[17] Ron, D.: Algorithmic and Analysis Techniques in Property Testing. In: Foundations and Trends in TCS (to appear) · Zbl 1184.68610
[18] Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing 25(2), 252–271 (1996) · Zbl 0844.68062 · doi:10.1137/S0097539793255151
[19] Sudan, M.: Invariance in Property Testing. ECCC, TR10-051 (2010)
[20] Sudan, M.: Testing Linear Properties: Some General Themes. ECCC, TR11-005 (2011)
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.