Property Testing of Massively Parametrized problems -- A survey <s> Testing monotonicity in general posets: <s> We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron (1996). The subject of this paper is testing regular languages. Our main result is as follows. For a regular language L/spl isin/{0, 1}* and an integer n there exists a randomized algorithm which always accepts a word w of length n if w/spl isin/L, and rejects it with high probability if w has to be modified in at least En positions to create a word in L. The algorithm queries O~(1//spl epsiv/) bits of w. This query complexity is shown to be optimal up to a factor poly-logarithmic in 1//spl epsiv/. We also discuss testability of more complex languages and show, in particular, that the query complexity required for testing context free languages cannot be bounded by any function of /spl epsiv/. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means. <s> BIB001 </s> Property Testing of Massively Parametrized problems -- A survey <s> Testing monotonicity in general posets: <s> The field of property testing studies algorithms that distinguish, using a small number of queries, between inputs which satisfy a given property, and those that are `far' from satisfying the property. Testing properties that are defined in terms of monotonicity has been extensively investigated, primarily in the context of the monotonicity of a sequence of integers, or the monotonicity of a function over the n-dimensional hypercube {1,l,m}n. These works resulted in monotonicity testers whose query complexity is at most polylogarithmic in the size of the domain.We show that in its most general setting, testing that Boolean functions are close to monotone is equivalent, with respect to the number of required queries, to several other testing problems in logic and graph theory. These problems include: testing that a Boolean assignment of variables is close to an assignment that satisfies a specific 2-CNF formula, testing that a set of vertices is close to one that is a vertex cover of a specific graph, and testing that a set of vertices is close to a clique.We then investigate the query complexity of monotonicity testing of both Boolean and integer functions over general partial orders. We give algorithms and lower bounds for the general problem, as well as for some interesting special cases. In proving a general lower bound, we construct graphs with combinatorial properties that may be of independent interest. <s> BIB002
Monotonicity testing in general posets generalizes monotonicity-testing of Boolean functions. Here a poset P = (V, ≤) is the given structure and the set of inputs is the collection of functions C V where C is typically a total ordered set (e.g., C = [n] with the natural order, and in particular the Boolean case n = 2) but could be taken as any poset. The fixed property here is the set of all functions that are monotone, namely all such f for which f (x) > C f (y) implies that x > P y. The main results in BIB002 are lower bounds for testing monotonicity for Boolean labeling of general posets, and in particular, a construction of some posets for which monotonicity requires relatively large query complexity (previous lower bounds where only for large range  ). In addition it is shown in BIB002 that monotonicity is testable when the poset is the transitive closure of an orientation of a tree (or a forest) and C is Boolean. It is also shown that there is a test with O(log |V |/ ) queries when P is the transitive closure of a directed acyclic graph (DAG) that as an undirected graph is of bounded tree-width BIB001 . There are some recent interesting generalization of the positive results above, as well as some improvements (E.g., for posets induced by planar graphs) in  , using 2TC-spanners. This will not be further described here.