Abstract
We survey property testing results for the so called ’massively parametrized’ model (or problems). The massively-parametrized framework studies problems such as: Given a graph G = (V,E), consider the property BI(G) containing all subgraphs of G that are bipartite.
Massively parametrized Properties, such as BI(G), are defined by two ingredients: a ’general’ property of inputs (e.g, ’being bipartite’ for the example above), and an underlying given structure (the graph G for the property BI(G)). Then the property is the restriction of the general property to inputs that are associated with the given structure.
In such situation, keeping the general property fixed and varying the underlying structure, the property and the corresponding tests might vary significantly in their structure. The focus of the study in this framework is how, for a fixed general property, the testing problem changes while changing the underlying structure.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N.: Testing subgraphs in large graphs. Random Struct. Algorithms 21(3-4), 359–370 (2002)
Alon, N., Krivelevich, M., Newman, I., Szegedy, M.: Regular languages are testable with a constant number of queries. SIAM Journal on Computing 30, 1842–1862 (2001)
Bhattacharyya, A., Grigorescu, E., Jung, K., Raskhodnikova, S., Woodruff, D.P.: Transitive-closure spanners. In: SODA, pp. 932–941 (2009)
Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: Some 3CNF properties are hard to test. SIAM J. Comput. 35(1), 1–21 (2005)
Bender, M.A., Ron, D.: Testing properties of directed graphs: acyclicity and connectivity. Random Struct. Algorithms 20(2), 184–205 (2002)
Chakraborty, S., Fischer, E., Lachish, O., Matsliah, A., Newman, I.: Testing s-t -connectivity. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol. 4627, pp. 380–394. Springer, Heidelberg (2007)
Dinur, I.: The PCP theorem by gap amplification. J. ACM 54(3), 12 (2007)
Fischer, E.: The art of uninformed decisions: A primer to property testing. BEATCS: Bulletin of the European Association for Theoretical Computer Science 75, 97–126 (2001)
Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. In: Proceedings of the 34th ACM STOC, pp. 474–483 (2002)
Fischer, E.: Personal communication
Fischer, E.: On the strength of comparisons in property testing. Inf. Comput. 189(1), 107–116 (2004)
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) (to appear in Algorithmica)
Fischer, E., Lachish, O., Newman, I., Rosenberg, E.: Lower bound technique for properties of underlying graphs. In Preparations
Fischer, E., Lachish, O., Nimbhorkar, P.: In Preparations
Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45(4), 653–750 (1998)
Halevy, S., Lachish, O., Newman, I., Tsur, D.: Testing orientation properties. Electronic Colloquium on Computational Complexity (ECCC) (153) (2005)
Halevy, S., Lachish, O., Newman, I., Tsur, D.: Testing properties of constraint-graphs. In: IEEE Conference on Computational Complexity, pp. 264–277 (2007)
Kostochka, A.: The minimum Hadwiger number for graphs with a given mean degree of vertices. Metody Diskret. Analiz. 38, 37–58 (1982)
Lachish, O., Newman, I., Shapira, A.: Space Complexity vs. Query Complexity. Computational Complexity 17(1), 70–93 (2008)
Newman, I.: Testing membership in languages that have small width branching programs. SIAM J. Comput. 31(5), 1557–1570 (2002)
Ron, D.: Property testing (A Tutorial). In: Rajasekaran, S., Pardalos, P.M., Reif, J.H., Rolin, J.D.P. (eds.) Handbook of Randomized Computing. Kluwer Press, Dordrecht (2001)
Thomason, A.: An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc. 95, 261–265 (1984)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Newman, I. (2010). Property Testing of Massively Parametrized Problems – A Survey. In: Goldreich, O. (eds) Property Testing. Lecture Notes in Computer Science, vol 6390. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16367-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-16367-8_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16366-1
Online ISBN: 978-3-642-16367-8
eBook Packages: Computer ScienceComputer Science (R0)